# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
486164 | 2021-11-10T16:27:09 Z | niloyroot | Experimental Charges (NOI19_charges) | C++14 | 29 ms | 3404 KB |
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<ll>; using pl = pair<ll,ll>; #define pb push_back #define form(m,it) for(auto it=m.begin(); it!=m.end(); it++) #define forp(i,a,b) for(ll i=a; i<=b; i++) #define forn(i,a,b) for(ll i=a; i>=b; i--) #define newl '\n' const ll mod = 1000000007; void solve(){ ll n; cin>>n; ll q; cin>>q; ll par[n+1]; ll sz[n+1]; bool col[n+1]; // whether it attracts it's parent or not; forp(i,1,n){ par[i]=i; sz[i]=1; col[i]=0; } char c; ll a,b,x,y; bool currA,currB; forp(i,1,q){ cin>>c>>a>>b; x=a;y=b; if(c!='Q'){ currA=(c=='A'); currB=0; while(a!=par[a]){ currA=(col[a]==1)?(currA^1):currA; a=par[a]; } while(b!=par[b]){ currB=(col[b]==1)?(currB^1):currB; b=par[b]; } if(a==b){continue;} if(sz[a]<sz[b]){swap(a,b);} sz[a]+=sz[b]; par[b]=a; col[b]=(currA!=currB); } else { currA=currB=0; while(a!=par[a]){ currA=(col[a]==0)?currA:(currA^1); a=par[a]; } while(b!=par[b]){ currB=(col[b]==0)?currB:(currB^1); b=par[b]; } if(a!=b){ cout<<'?'<<newl; } else { if(currA!=currB){ cout<<"A"<<newl; } else { cout<<"R"<<newl; } } } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int t=1; //cin>>t; while(t--)solve(); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 2764 KB | Output is correct |
2 | Correct | 16 ms | 2764 KB | Output is correct |
3 | Correct | 21 ms | 2764 KB | Output is correct |
4 | Correct | 21 ms | 2760 KB | Output is correct |
5 | Correct | 18 ms | 2800 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 3364 KB | Output is correct |
2 | Correct | 21 ms | 3252 KB | Output is correct |
3 | Correct | 24 ms | 3244 KB | Output is correct |
4 | Correct | 24 ms | 3276 KB | Output is correct |
5 | Correct | 23 ms | 3404 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 3276 KB | Output is correct |
2 | Correct | 21 ms | 3232 KB | Output is correct |
3 | Correct | 22 ms | 3116 KB | Output is correct |
4 | Correct | 29 ms | 3312 KB | Output is correct |
5 | Correct | 25 ms | 3168 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 2 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 332 KB | Output is correct |
8 | Correct | 1 ms | 328 KB | Output is correct |
9 | Correct | 1 ms | 332 KB | Output is correct |
10 | Correct | 1 ms | 324 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 15 ms | 2764 KB | Output is correct |
7 | Correct | 16 ms | 2764 KB | Output is correct |
8 | Correct | 21 ms | 2764 KB | Output is correct |
9 | Correct | 21 ms | 2760 KB | Output is correct |
10 | Correct | 18 ms | 2800 KB | Output is correct |
11 | Correct | 24 ms | 3364 KB | Output is correct |
12 | Correct | 21 ms | 3252 KB | Output is correct |
13 | Correct | 24 ms | 3244 KB | Output is correct |
14 | Correct | 24 ms | 3276 KB | Output is correct |
15 | Correct | 23 ms | 3404 KB | Output is correct |
16 | Correct | 20 ms | 3276 KB | Output is correct |
17 | Correct | 21 ms | 3232 KB | Output is correct |
18 | Correct | 22 ms | 3116 KB | Output is correct |
19 | Correct | 29 ms | 3312 KB | Output is correct |
20 | Correct | 25 ms | 3168 KB | Output is correct |
21 | Correct | 2 ms | 332 KB | Output is correct |
22 | Correct | 1 ms | 332 KB | Output is correct |
23 | Correct | 1 ms | 328 KB | Output is correct |
24 | Correct | 1 ms | 332 KB | Output is correct |
25 | Correct | 1 ms | 324 KB | Output is correct |
26 | Correct | 20 ms | 3256 KB | Output is correct |
27 | Correct | 26 ms | 3244 KB | Output is correct |
28 | Correct | 21 ms | 3148 KB | Output is correct |
29 | Correct | 27 ms | 3024 KB | Output is correct |
30 | Correct | 21 ms | 3164 KB | Output is correct |