Submission #2913366


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
struct UnionFind {vector<int> par; // uf(x,y)->y
UnionFind(int NV) { par.clear(); rep(i, 0, NV) par.push_back(i); }
void reset() { rep(i, 0, par.size()) par[i] = i; }
int operator[](int x) { return par[x] == x ? x : par[x] = operator[](par[x]); }
void operator()(int x, int y) {x = operator[](x); y = operator[](y);if (x != y) par[x] = y;}};
/*---------------------------------------------------------------------------------------------------
           _
     _ ´<_   Welcome to My Coding Space!
     ´_` /  ⌒i
           | |
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
struct UnionFind {vector<int> par; // uf(x,y)->y
    UnionFind(int NV) { par.clear(); rep(i, 0, NV) par.push_back(i); }
    void reset() { rep(i, 0, par.size()) par[i] = i; }
    int operator[](int x) { return par[x] == x ? x : par[x] = operator[](par[x]); }
    void operator()(int x, int y) {x = operator[](x); y = operator[](y);if (x != y) par[x] = y;}};
/*---------------------------------------------------------------------------------------------------
            ∧_∧  
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     
    /   \     | |     
    /   / ̄ ̄ ̄ ̄/  |  
  __(__ニつ/     _/ .| .|____  
     \/____/ (u ⊃  
---------------------------------------------------------------------------------------------------*/




int N, Q;
vector<int> gr[101010];
set<int> E[101010];
//---------------------------------------------------------------------------------------------------
#define yes "Yes"
#define no "No"
void _main() {
    cin >> N >> Q;

    UnionFind connect(N);
    UnionFind complete(N);
    rep(i, 0, N) gr[i].push_back(i);

    rep(_, 0, Q) {
        int type, u, v; cin >> type >> u >> v;
        u--; v--;

        if (type == 1) {
            E[u].insert(v);
            E[v].insert(u);

            if (complete[u] == complete[v]) continue;
            if (connect[u] == connect[v]) continue;

            int uu = connect[u];
            int vv = connect[v];

            if (gr[uu].size() > gr[vv].size()) swap(gr[uu], gr[vv]);
            fore(i, gr[uu]) gr[vv].push_back(i);

            connect(uu, vv);
        }
        else if (type == 2) {
            int uu = connect[u];

            int n = gr[uu].size();
            rep(i, 1, n) complete(gr[uu][0], gr[uu][i]);

            int top = gr[uu][0];
            gr[uu].clear();
            gr[uu].push_back(top);
        }
        else {
            string ans = no;
            if (complete[u] == complete[v]) ans = yes;
            if (E[u].count(v)) ans = yes;
            printf("%s\n", ans.c_str());
        }
    }
}

Submission Info

Submission Time
Task D - Propagating Edges
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 800
Code Size 2937 Byte
Status AC
Exec Time 127 ms
Memory 20088 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 3
AC × 37
Set Name Test Cases
Sample example_0, example_1, example_2
All bigrand_0, bigrand_1, bigrand_2, bigrand_3, bigrand_4, comp_0, comp_1, comp_2, comp_3, example_0, example_1, example_2, rand_0, rand_1, rand_10, rand_11, rand_2, rand_3, rand_4, rand_5, rand_6, rand_7, rand_8, rand_9, randcomp_0, randcomp_1, randcomp_2, randcomp_3, randcomp_4, tenc_0, tenc_1, tenc_2, tenc_3, tree_0, tree_1, tree_2, tree_3
Case Name Status Exec Time Memory
bigrand_0 AC 123 ms 17784 KB
bigrand_1 AC 121 ms 17656 KB
bigrand_2 AC 120 ms 17784 KB
bigrand_3 AC 114 ms 17400 KB
bigrand_4 AC 124 ms 17528 KB
comp_0 AC 105 ms 14712 KB
comp_1 AC 105 ms 15096 KB
comp_2 AC 106 ms 14840 KB
comp_3 AC 105 ms 15096 KB
example_0 AC 4 ms 7424 KB
example_1 AC 4 ms 7424 KB
example_2 AC 4 ms 7424 KB
rand_0 AC 4 ms 7424 KB
rand_1 AC 4 ms 7424 KB
rand_10 AC 4 ms 7424 KB
rand_11 AC 4 ms 7424 KB
rand_2 AC 4 ms 7424 KB
rand_3 AC 4 ms 7424 KB
rand_4 AC 4 ms 7424 KB
rand_5 AC 4 ms 7424 KB
rand_6 AC 4 ms 7424 KB
rand_7 AC 4 ms 7424 KB
rand_8 AC 4 ms 7424 KB
rand_9 AC 4 ms 7424 KB
randcomp_0 AC 106 ms 19320 KB
randcomp_1 AC 116 ms 20088 KB
randcomp_2 AC 118 ms 19320 KB
randcomp_3 AC 127 ms 20088 KB
randcomp_4 AC 112 ms 19320 KB
tenc_0 AC 89 ms 14840 KB
tenc_1 AC 87 ms 14968 KB
tenc_2 AC 83 ms 14840 KB
tenc_3 AC 99 ms 14968 KB
tree_0 AC 95 ms 14328 KB
tree_1 AC 93 ms 14584 KB
tree_2 AC 99 ms 15224 KB
tree_3 AC 98 ms 15352 KB


2025-01-21 (Tue)
17:38:25 +00:00