Submission #653873

#TimeUsernameProblemLanguageResultExecution timeMemory
653873true22Experimental Charges (NOI19_charges)C++14
14 / 100
29 ms2748 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); 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 a, ll b){ /* this is symmetric the enemy of c1 is united with rep of c1 and vice versa */ a = find(a); b = find(b); if (eof[a] == -1) eof[a] = b; else unite(eof[a], b); if (eof[b] == -1) eof[b] = eof[a]; else unite(eof[b], a); } bool same(ll a, ll b){ return (find(a) == find(b)); } bool attract(ll a, ll b){ if (eof[a] == -1) return 0; return same(eof[a], b); } void query(ll a, ll b){ if (same(a, b)){ cout << 'R' << nl; return; } if (attract(a, b)){ cout << 'A' << nl; return; } cout << '?' << nl; } 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{ if (same(a, b)){ cout << "R" << nl; continue; } if (same(eof[find(a)], b)){ cout << "A" << nl; continue; } if (eof[find(a)] == -1){ cout << "?" << nl; continue; } } } // cout << find(2) << ' ' << find(4) << nl; // cout << eof[find(2)] << nl; // bv(same(eof[find(2)], 4)); } int main(){ ios::sync_with_stdio(0); cin.tie(0); 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...