Submission #101820
Source Code Expand
#include<iostream> #include<vector> #include<map> #include<set> #include<algorithm> #define rep(i, n) for(int i = 0; i < (n); ++i) #define mp make_pair #define all(v) (v).begin(), (v).end() using namespace std; typedef pair<int, int> pii; struct UnionFind{ vector<int> par, ran; int n; UnionFind(int x=0){init(x);} void init(int x){ n = x; par.resize(x); ran.resize(x); fill(all(ran), 1); fill(all(par), -1); } int find(int x){ if(par[x] < 0) return x; return par[x] = find(par[x]); } bool same(int x, int y){ return find(x) == find(y); } bool unite(int x, int y){ x = find(x); y = find(y); if(x == y) return false; if(ran[x] == ran[y]) ++ran[x]; if(ran[x] < ran[y]) swap(x, y); par[x] += par[y]; par[y] = x; return true; } }; typedef pair<int, pii> Q; int main(void){ int n, m, k; cin >> n >> m >> k; vector<pii> edges; set<int> del; vector<Q> query; rep(i, m){ int a, b; cin >> a >> b; --a; --b; edges.push_back(make_pair(min(a, b), max(a, b))); } rep(i, k){ int type; cin >> type; if(type == 0){ int e; cin >> e; --e; del.insert(e); query.push_back(mp(0, edges[e])); }else{ int u, v; cin >> u >> v; --u; --v; query.push_back(mp(1, mp(min(u, v), max(u, v)))); } } UnionFind uf(n); rep(i, m){ if(!del.count(i)) uf.unite(edges[i].first, edges[i].second); } vector<int> res; for(int i = k-1; i >= 0; --i){ if(query[i].first == 0){ uf.unite(query[i].second.first, query[i].second.second); }else{ res.push_back(uf.same(query[i].second.first, query[i].second.second)); } } reverse(all(res)); for(int i = 0; i < res.size(); ++i){ if(res[i]){ cout << "YES" << endl; }else{ cout << "NO" << endl; } } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Graph Destruction |
User | nikyaudo |
Language | C++ (G++ 4.6.4) |
Score | 100 |
Code Size | 1830 Byte |
Status | AC |
Exec Time | 548 ms |
Memory | 5512 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 30, 31, 32, 33, 34, 35, 36, 4, 5, 50, 6, 7, 8, 9 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
1 | AC | 22 ms | 736 KB |
10 | AC | 31 ms | 936 KB |
11 | AC | 70 ms | 1308 KB |
12 | AC | 170 ms | 2148 KB |
13 | AC | 310 ms | 3408 KB |
14 | AC | 461 ms | 4176 KB |
15 | AC | 507 ms | 4864 KB |
16 | AC | 548 ms | 5512 KB |
17 | AC | 176 ms | 2524 KB |
18 | AC | 162 ms | 2396 KB |
19 | AC | 206 ms | 2864 KB |
2 | AC | 21 ms | 804 KB |
20 | AC | 292 ms | 3796 KB |
21 | AC | 202 ms | 2772 KB |
22 | AC | 285 ms | 3792 KB |
23 | AC | 206 ms | 2776 KB |
24 | AC | 140 ms | 2208 KB |
25 | AC | 160 ms | 2332 KB |
26 | AC | 425 ms | 5104 KB |
27 | AC | 135 ms | 2144 KB |
28 | AC | 150 ms | 2264 KB |
29 | AC | 332 ms | 4136 KB |
3 | AC | 21 ms | 804 KB |
30 | AC | 250 ms | 3284 KB |
31 | AC | 409 ms | 4892 KB |
32 | AC | 329 ms | 4164 KB |
33 | AC | 352 ms | 4432 KB |
34 | AC | 434 ms | 5140 KB |
35 | AC | 388 ms | 4688 KB |
36 | AC | 182 ms | 2524 KB |
4 | AC | 21 ms | 928 KB |
5 | AC | 23 ms | 808 KB |
50 | AC | 411 ms | 4888 KB |
6 | AC | 24 ms | 804 KB |
7 | AC | 23 ms | 800 KB |
8 | AC | 24 ms | 928 KB |
9 | AC | 27 ms | 788 KB |