Japan Alumni Group Summer Camp 2013 Warming Up

Submission #1059212

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);++i)
#define rep2(i,a,b) for (int i=(a);i<(b);++i)
#define rrep(i,n) for (int i=(n)-1;i>=0;--i)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;--i)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(_v) cout<<(#_v)<<":";for(auto(_x):(_v)){cout<<" "<<(_x);}cout<<endl;
#define printVS(vs) cout<<(#vs)<<":"<<endl;for(auto(s):(vs)){cout<<(s)<< endl;}
#define printVV(vv) cout<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cout<<" "<<(x);}cout<<endl;}
#define printP(p) cout<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cout<<(#vp)<<":"<<endl;for(auto(p):(vp)){cout<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cout << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cout << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 1ll << 60;
const int mod = 1e9 + 7;
using Graph = vector<vector<int>>;

class UnionFind {
private:
    const int n;
    vector<int> uni;
public:
    UnionFind(int _n) : n(_n), uni(_n, -1) {}
    int root(int x) {
        if (uni[x] < 0) return x;
        return uni[x] = root(uni[x]);
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (uni[x] > uni[y]) swap(x, y);
        uni[x] += uni[y];
        uni[y] = x;
        return true;
    }
    int getSize(int x) {
        return -uni[root(x)];
    }
    void print() {
        for (auto x : uni) cout << x << " ";
        cout << endl;
    }
};

main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n, m, k;
    cin >> n >> m >> k;

    vector<Pii> edges;
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        edges.emplace_back(a, b);
    }

    vector<bool> alive(m, true);
    vector<vector<int>> queries;
    rep(i, k) {
        int t;
        cin >> t;
        if (!t) {
            int e;
            cin >> e;
            e--;
            queries.emplace_back(vector<int>{t, e});
            alive[e] = false;
        }
        else {
            int a, b;
            cin >> a >> b;
            a--; b--;
            queries.emplace_back(vector<int>{t, a, b});
        }
    }
    reverse(all(queries));

    UnionFind uf(n);
    rep(i, m) {
        if (alive[i]) {
            uf.unite(edges[i].first, edges[i].second);
        }
    }

    vector<string> ans;
    for (auto q : queries) {
        if (!q[0]) {
            uf.unite(edges[q[1]].first, edges[q[1]].second);
        }
        else {
            ans.emplace_back(uf.same(q[1], q[2]) ? "YES" : "NO");
        }
    }
    reverse(all(ans));

    for (auto s : ans) {
        cout << s << endl;
    }
}

Submission

Task問題 D - Graph Destruction
User nameユーザ名 yurahuna
Created time投稿日時
Language言語 C++11 (GCC 4.8.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 3276 Byte
File nameファイル名
Exec time実行時間 253 ms
Memory usageメモリ使用量 12944 KB

Test case

Set

Set name Score得点 / Max score Cases
All 100 / 100 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
1 AC 18 ms 804 KB
10 AC 23 ms 1056 KB
11 AC 42 ms 2268 KB
12 AC 92 ms 4520 KB
13 AC 159 ms 8036 KB
14 AC 224 ms 11108 KB
15 AC 238 ms 12052 KB
16 AC 253 ms 12944 KB
17 AC 86 ms 4556 KB
18 AC 79 ms 4264 KB
19 AC 99 ms 5352 KB
2 AC 18 ms 800 KB
20 AC 136 ms 7432 KB
21 AC 100 ms 5396 KB
22 AC 134 ms 7308 KB
23 AC 101 ms 5484 KB
24 AC 72 ms 3884 KB
25 AC 81 ms 4392 KB
26 AC 193 ms 10508 KB
27 AC 70 ms 3756 KB
28 AC 77 ms 4044 KB
29 AC 155 ms 8420 KB
3 AC 18 ms 800 KB
30 AC 118 ms 6504 KB
31 AC 188 ms 10248 KB
32 AC 161 ms 8336 KB
33 AC 167 ms 8976 KB
34 AC 189 ms 10504 KB
35 AC 176 ms 9744 KB
36 AC 93 ms 4876 KB
4 AC 18 ms 800 KB
5 AC 18 ms 804 KB
50 AC 191 ms 10248 KB
6 AC 17 ms 800 KB
7 AC 20 ms 804 KB
8 AC 20 ms 804 KB
9 AC 21 ms 928 KB