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)->yUnionFind(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/ \ | |
#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 |
|
|
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 |