結果
問題 | No.416 旅行会社 |
ユーザー | latte0119 |
提出日時 | 2016-08-26 22:36:12 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 1,203 ms / 4,000 ms |
コード長 | 3,156 bytes |
コンパイル時間 | 1,605 ms |
コンパイル使用メモリ | 162,848 KB |
実行使用メモリ | 123,688 KB |
最終ジャッジ日時 | 2023-08-21 09:39:45 |
合計ジャッジ時間 | 10,838 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 271 ms
117,784 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 3 ms
4,376 KB |
testcase_08 | AC | 7 ms
5,104 KB |
testcase_09 | AC | 39 ms
12,416 KB |
testcase_10 | AC | 278 ms
117,788 KB |
testcase_11 | AC | 257 ms
117,788 KB |
testcase_12 | AC | 275 ms
117,968 KB |
testcase_13 | AC | 258 ms
117,840 KB |
testcase_14 | AC | 1,203 ms
123,380 KB |
testcase_15 | AC | 780 ms
123,532 KB |
testcase_16 | AC | 668 ms
123,688 KB |
testcase_17 | AC | 827 ms
123,588 KB |
testcase_18 | AC | 905 ms
123,688 KB |
testcase_19 | AC | 643 ms
113,732 KB |
testcase_20 | AC | 934 ms
113,408 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; #define int long long typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define all(v) (v).begin(),(v).end() #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define pb push_back #define fi first #define se second template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} class Array { public: Array() {} Array(int n) { h = 0; for (int i = 1; i < n; i *= 8) h += 3; } int *mutable_get(int k) { auto p = mutable_get(k, root, 0, h); root = p.first; return &p.second->value; } int operator[](int k) { node *res = immutable_get(k, root, 0, h); return res != nullptr ? res->value : -1; } private: struct node { node *ch[8] = {}; int value = -1; }; int h; node *root = nullptr; node *immutable_get(int a, node *x, int l, int d) { if (x == nullptr) return x; if (d == 0) return x; int id = (a - l) >> (d - 3); return immutable_get(a, x->ch[id], l + (id << (d - 3)), d - 3); } pair<node *, node *> mutable_get(int a, node *x, int l, int d) { x = x != nullptr ? new node(*x) : new node(); if (d == 0) return make_pair(x, x); int id = (a - l) >> (d - 3); auto p = mutable_get(a, x->ch[id], l + (id << (d - 3)), d - 3); x->ch[id] = p.first; return make_pair(x, p.second); } }; // root: O(logN loglogN) // merge: O(logN loglogN) struct UnionFind { Array uf; UnionFind() : uf(0) {} UnionFind(int n) : uf(n) {} int root(int x) { int nd = uf[x]; if (nd < 0) return x; return root(nd); } void merge(int x, int y) { x = root(x); y = root(y); if (x == y) return; int *u = uf.mutable_get(x); int *v = uf.mutable_get(y); if (-*u < -*v) swap(u, v), swap(x, y); *u += *v; *v = x; } int size(int x) { return -uf[root(x)]; } int query(int x, int y) { x = root(x); y = root(y); if (x == y) { return -uf[x]; } else { return -uf[x] - uf[y]; } } }; int N,M,Q; int C[222222],D[222222]; signed main(){ scanf("%lld%lld%lld",&N,&M,&Q); vpint es; rep(i,M){ int a,b; scanf("%lld%lld",&a,&b); a--;b--; if(a>b)swap(a,b); es.pb(pint(a,b)); } sort(all(es)); vint used(M,0); rep(i,Q){ scanf("%lld%lld",&C[i],&D[i]); C[i]--;D[i]--; if(C[i]>D[i])swap(C[i],D[i]); int tmp=lower_bound(all(es),pint(C[i],D[i]))-es.begin(); used[tmp]=true; } vector<UnionFind>ufs(Q+1); UnionFind uf(N); rep(i,M)if(!used[i])uf.merge(es[i].fi,es[i].se); ufs[Q]=uf; for(int i=Q-1;i>=0;i--){ uf.merge(C[i],D[i]); ufs[i]=uf; } reps(i,1,N){ int lb=-1,ub=Q+1; while(ub-lb>1){ int mid=(ub+lb)/2; if(ufs[mid].root(0)==ufs[mid].root(i)){ lb=mid; } else{ ub=mid; } } if(ub==Q+1)puts("-1"); else printf("%lld\n",ub); } return 0; }