Submission #653866

#TimeUsernameProblemLanguageResultExecution timeMemory
653866true22Experimental Charges (NOI19_charges)C++14
21 / 100
33 ms4100 KiB
#include <bits/stdc++.h> using namespace std; // short forms // #define nl "\n" #define pb push_back #define f first #define s second #define ll long long int #define ld long double #define mp make_pair #define all(x) x.begin(), x.end() // debug // #define pv(x) for(auto k : x){cout << k << " ";} cout << nl; #define pp(x) cout << x.f << " " << x.s << nl; #define bv(x) if (x) cout << "true"; else cout << "false"; #define gp(x, y) x << " " << y // loop // #define FOR(i, a, b) for(ll i = a; i <=b; i++) // pair // typedef pair<ll, ll> pl; // vector // typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<pl> vp; // constants // const ll INF = 1e17; const ll mod = 1e9 + 7; const ll S = 1e5 + 5; ll n, siz[S], link[S], eof[S]; ll find(ll a){ ll st = a; while(a != link[a]) a = link[a]; //path compression while(st != link[st]){ ll tmp = link[st]; link[st] = a; st = tmp; } return a; } bool unite(ll a, ll b){ a = find(a); b = find(b); if (a == b) return 0; // union by size if (siz[a] < siz[b]) swap(a, b); siz[a] += siz[b]; link[b] = a; return 1; } void set_same(ll a, ll b){ /* 1) unite the friends 2) unite the enemies of the friends 3) copy the link */ a = find(a); b = find(b); if (siz[a] < siz[b]) swap(a, b); // a is the bigger set unite(a, b); if (eof[a] != -1 && eof[b] != -1) unite(eof[a], eof[b]); if (eof[a] == -1) eof[a] = eof[b]; } void set_op(ll c1, ll c2){ /* Most importantly, this is symmetric so the enemy of c1 is united with rep of c1 and vice versa */ ll set1 = find(c1); ll set2 = find(c2); ll e = eof[set1]; if (e == -1) eof[set1] = c2; else unite(e, c2); e = eof[set2]; if (e == -1) eof[set2] = c1; else unite(e, c1); } void query(ll a, ll b){ a = find(a); b = find(b); if (a == b){ cout << 'R' << nl; return; // repel } if (find(eof[a]) == b){ cout << 'A' << nl; return; // attract } if (eof[a] == -1){ cout << '?' << nl; return; } } void solve(){ FOR(i, 0, S-1){ link[i] = i; siz[i] = 1; eof[i] = -1; } ll q; cin >> n >> q; while(q--){ char t; ll a, b; cin >> t; cin >> a >> b; if (t == 'A'){ set_op(a, b); }else if (t == 'R'){ set_same(a, b); }else{ // cout << "for " << gp(a, b) << nl; // cout << find(a) << ' ' << find(b) << nl; query(a, b); } } } int main(){ ios::sync_with_stdio(0); cin.tie(0); ll t = 1; //cin >> t; while(t--){ solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...