Submit Info #1042

Problem Lang User Status Time Memory
Directed MST cpp chocorusk WA 116 ms 16.24 MiB

ケース詳細
Name Status Time Memory
example_00 AC 9 ms 0.64 MiB
example_01 AC 7 ms 0.64 MiB
random_00 AC 114 ms 12.43 MiB
random_01 WA 114 ms 14.38 MiB
random_02 WA 114 ms 12.50 MiB
random_03 AC 116 ms 16.24 MiB
random_04 WA 64 ms 8.01 MiB

#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <stack> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; struct unionfind{ vector<int> par, rk; unionfind() {} unionfind(int n):par(n), rk(n, 0){ for(int i=0; i<n; i++) par[i]=i; } int find(int x){ if(par[x]==x) return x; return par[x]=find(par[x]); } bool unite(int x, int y){ x=find(x); y=find(y); if(x==y) return false; if(rk[x]>rk[y]) swap(x, y); par[x]=y; if(rk[x]==rk[y]) rk[y]++; return true; } bool same(int x, int y){ return find(x)==find(y); } }; template<typename T, typename E=T, bool ismin=true> struct SkewHeap{ using G=function<T(T, E)>; using H=function<E(E, E)>; struct Node{ T key; E lazy; Node *l, *r; }; const G g; const H h; SkewHeap(const G &g, const H &h):g(g), h(h){} Node *propagate(Node *t){ if(t->lazy!=0){ if(t->l) t->l->lazy=h(t->l->lazy, t->lazy); if(t->r) t->r->lazy=h(t->r->lazy, t->lazy); t->key=g(t->key, t->lazy); t->lazy=0; } return t; } Node *merge(Node *x, Node *y){ if(!x) return y; if(!y) return x; propagate(x); propagate(y); if((x->key < y->key)^ismin) swap(x, y); x->r=merge(x->r, y); swap(x->l, x->r); return x; } void push(Node *&root, const T &key){ root=merge(root, new Node({key, 0, nullptr, nullptr})); } T top(Node *&root){ return propagate(root)->key; } T pop(Node *&root){ T top=propagate(root)->key; auto *temp=root; root=merge(root->l, root->r); delete temp; return top; } bool empty(Node *root) const{ return !root; } void add(Node *root, const E &lazy){ if(root){ root->lazy=h(root->lazy, lazy); propagate(root); } } Node *makeheap(){ return nullptr; } }; struct edge{ int from, to; ll cost; edge(){} edge(int from, int to, ll cost):from(from), to(to), cost(cost){} }; int n; vector<edge> edges; vector<int> tree; ll DirectedMST(int r){ ll ret=0; vector<int> used(n); unionfind uf(n); used[r]=2; using Pi=pair<ll, P>; using Heap=SkewHeap<Pi, ll>; using Node=Heap::Node; auto g=[](Pi a, ll b){ return Pi(a.first+b, a.second);}; auto h=[](ll a, ll b){ return a+b;}; Heap heap(g, h); vector<Node*> heaps(n, heap.makeheap()); for(auto e:edges){ heap.push(heaps[e.to], Pi(e.cost, P(e.from, e.to))); } for(int i=0; i<n; i++){ if(used[i]!=0) continue; int cur=i; stack<int> processing; while(used[cur]!=2){ processing.push(cur); used[cur]=1; if(heap.empty(heaps[cur])) return -1; auto p=heap.top(heaps[cur]); heap.add(heaps[cur], -p.first); heap.pop(heaps[cur]); ret+=p.first; tree[p.second.second]=p.second.first; int v=p.second.first; if(used[uf.find(v)]==1){ int w; Node *merged=heap.makeheap(); do{ w=processing.top(); processing.pop(); used[w]=2; merged=heap.merge(merged, heaps[w]); }while(uf.unite(v, w)); heaps[uf.find(v)]=merged; used[uf.find(v)]=1; } cur=uf.find(v); } while(!processing.empty()){ used[processing.top()]=2; processing.pop(); } } return ret; } int main() { int m, r; scanf("%d %d %d", &n, &m, &r); edges.resize(m); for(int i=0; i<m; i++){ int a, b; ll c; scanf("%d %d %lld", &a, &b, &c); edges[i]=edge(a, b, c); } tree.resize(n); tree[r]=r; ll ans=DirectedMST(r); printf("%lld\n", ans); for(int i=0; i<n; i++){ printf("%d ", tree[i]); } printf("\n"); return 0; }