Submission #101973
Source Code Expand
#include <cstdio>
#include <vector>
#include <utility>
#include <queue>
#include <map>
using namespace std;
typedef pair<int, int> pii;
typedef pair<pii, pii> ppp;
struct Query {
int t, a, b;
};
class UnionFindTree {
private:
vector<int> parent;
vector<int> rank;
public:
explicit UnionFindTree(int n = 0) :
parent(n), rank(n)
{
for(int i = 0; i < n; ++i){ parent[i] = i; }
}
int find(int x){
if(parent[x] == x){ return x; }
parent[x] = find(parent[x]);
return parent[x];
}
int unite(int x, int y){
x = find(x);
y = find(y);
if(x == y){ return x; }
if(rank[x] < rank[y]){
parent[x] = y;
return y;
}else if(rank[x] > rank[y]){
parent[y] = x;
return x;
}else{
parent[y] = x;
++rank[x];
return x;
}
}
bool same(int x, int y){
return find(x) == find(y);
}
};
int main(){
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
vector<pii> edges(m);
for(int i = 0; i < m; ++i){
int a, b;
scanf("%d%d", &a, &b);
edges[i] = pii(a - 1, b - 1);
}
const int SQRT_N = 500;
vector<int> destructed(m);
for(int i = 0; i < k; i += SQRT_N){
vector<Query> queries;
for(int j = 0; j < SQRT_N && i + j < k; ++j){
Query q;
scanf("%d%d", &q.t, &q.a);
if(q.t == 0){
--q.a;
destructed[q.a] = 1;
}else if(q.t == 1){
scanf("%d", &q.b);
--q.a; --q.b;
}
queries.push_back(q);
}
UnionFindTree uft(n);
for(int j = 0; j < m; ++j){
if(destructed[j]){ continue; }
uft.unite(edges[j].first, edges[j].second);
}
vector<bool> appeared(n);
for(int j = 0; j < queries.size(); ++j){
const Query &q = queries[j];
if(q.t == 0){ continue; }
const int a = uft.find(q.a), b = uft.find(q.b);
appeared[a] = appeared[b] = true;
}
vector< vector<int> > conn(n);
vector<ppp> rem(queries.size());
for(int j = 0; j < queries.size(); ++j){
Query &q = queries[j];
if(q.t != 0){ continue; }
const int a = uft.find(edges[q.a].first);
const int b = uft.find(edges[q.a].second);
if(a == b){
q.t == 2;
}else if(!appeared[a] || !appeared[b]){
q.t == 2;
}
rem[j].first = pii(a, conn[a].size());
rem[j].second = pii(b, conn[b].size());
conn[a].push_back(b);
conn[b].push_back(a);
}
vector<int> passed(n, -1);
for(int j = 0; j < queries.size(); ++j){
const Query &q = queries[j];
if(q.t == 0){
const pii p0 = rem[j].first, p1 = rem[j].second;
const int a = uft.find(p0.first);
const int b = uft.find(p1.first);
if(a == b){ continue; }
conn[p0.first][p0.second] = p0.first;
conn[p1.first][p1.second] = p1.first;
}else{
const int a = uft.find(q.a), b = uft.find(q.b);
queue<int> que;
que.push(a);
passed[a] = j;
bool reach = (a == b);
while(!reach && !que.empty()){
const int v = que.front();
que.pop();
for(int l = 0; l < conn[v].size(); ++l){
const int u = conn[v][l];
if(u == b){ reach = true; break; }
if(passed[u] >= j){ continue; }
passed[u] = j;
que.push(u);
}
}
puts(reach ? "YES" : "NO");
}
}
}
return 0;
}
Submission Info
Submission Time
2013-09-21 12:39:29+0900
Task
D - Graph Destruction
User
neteru_AA
Language
C++ (G++ 4.6.4)
Score
100
Code Size
3204 Byte
Status
AC
Exec Time
1172 ms
Memory
5724 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:55:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:59:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:68:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:73:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
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
800 KB
10
AC
23 ms
804 KB
11
AC
32 ms
796 KB
12
AC
62 ms
996 KB
13
AC
112 ms
1188 KB
14
AC
206 ms
1880 KB
15
AC
659 ms
3872 KB
16
AC
1172 ms
5724 KB
17
AC
92 ms
1452 KB
18
AC
85 ms
1380 KB
19
AC
117 ms
1772 KB
2
AC
21 ms
736 KB
20
AC
184 ms
1872 KB
21
AC
116 ms
1736 KB
22
AC
178 ms
1816 KB
23
AC
116 ms
1512 KB
24
AC
74 ms
1392 KB
25
AC
87 ms
1524 KB
26
AC
399 ms
2292 KB
27
AC
70 ms
1316 KB
28
AC
80 ms
1332 KB
29
AC
211 ms
1796 KB
3
AC
20 ms
676 KB
30
AC
140 ms
1572 KB
31
AC
297 ms
2076 KB
32
AC
206 ms
1668 KB
33
AC
248 ms
2028 KB
34
AC
414 ms
2264 KB
35
AC
267 ms
1988 KB
36
AC
99 ms
1520 KB
4
AC
21 ms
800 KB
5
AC
21 ms
800 KB
50
AC
291 ms
1996 KB
6
AC
22 ms
800 KB
7
AC
21 ms
804 KB
8
AC
21 ms
808 KB
9
AC
22 ms
808 KB