Submission #101809


Source Code Expand

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int a[100000];
int par[100000];

int find(int x)
{
    if (par[x] == x) return x;
    
    return par[x] = find(par[x]);
}

void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    
    if (x == y) return;
    
    par[x] = y;
}

int main()
{
    int n, m, k, i;
    vector <pair<int, int> > v;
    vector <pair<int, pair<int, int> > > w;
    vector <int> z;
    
    scanf("%d %d %d", &n, &m, &k);
    
    for (i = 0; i < m; i++) {
        int x, y;
        
        scanf("%d %d", &x, &y);
        
        x--;
        y--;
        
        v.push_back(make_pair(x, y));
    }
    
    for (i = 0; i < n; i++) par[i] = i;
    
    for (i = 0; i < k; i++) {
        int x, y, z;
        
        scanf("%d", &x);
        
        if (x == 0) {
            scanf("%d", &y);
        } else {
            scanf("%d %d", &y, &z);
        }
        
        y--;
        z--;
        
        if (x == 0) a[y] = 1;
        
        w.push_back(make_pair(x, make_pair(y, z)));
    }
    
    for (i = 0; i < m; i++) {
        if (a[i] == 0) unite(v[i].first, v[i].second);
    }
    
    for (i = k - 1; i >= 0; i--) {
        if (w[i].first == 0) {
            unite(v[w[i].second.first].first, v[w[i].second.first].second);
        } else {
            if (find(w[i].second.first) == find(w[i].second.second)) {
                z.push_back(0);
            } else {
                z.push_back(1);
            }
        }
    }
    
    reverse(z.begin(), z.end());
    
    for (i = 0; i < z.size(); i++) {
        if (z[i] == 0) {
            puts("YES");
        } else {
            puts("NO");
        }
    }
    
    return 0;
}

Submission Info

Submission Time
Task D - Graph Destruction
User not_shiokawa
Language C++ (GCC 4.4.7)
Score 100
Code Size 1817 Byte
Status AC
Exec Time 115 ms
Memory 4632 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:52: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:55: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:57: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 37
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 21 ms 928 KB
10 AC 22 ms 800 KB
11 AC 28 ms 1232 KB
12 AC 41 ms 1820 KB
13 AC 62 ms 2588 KB
14 AC 80 ms 3340 KB
15 AC 97 ms 3860 KB
16 AC 115 ms 4632 KB
17 AC 45 ms 1824 KB
18 AC 45 ms 1816 KB
19 AC 53 ms 1944 KB
2 AC 21 ms 800 KB
20 AC 69 ms 2828 KB
21 AC 51 ms 1948 KB
22 AC 66 ms 2836 KB
23 AC 52 ms 1944 KB
24 AC 40 ms 1560 KB
25 AC 43 ms 1892 KB
26 AC 93 ms 3356 KB
27 AC 42 ms 1504 KB
28 AC 43 ms 1828 KB
29 AC 72 ms 2832 KB
3 AC 21 ms 740 KB
30 AC 60 ms 2320 KB
31 AC 88 ms 3224 KB
32 AC 75 ms 2840 KB
33 AC 86 ms 3092 KB
34 AC 91 ms 3356 KB
35 AC 83 ms 3228 KB
36 AC 48 ms 1956 KB
4 AC 21 ms 808 KB
5 AC 20 ms 796 KB
50 AC 88 ms 3232 KB
6 AC 20 ms 804 KB
7 AC 20 ms 804 KB
8 AC 21 ms 804 KB
9 AC 22 ms 800 KB