Submission #718242

#TimeUsernameProblemLanguageResultExecution timeMemory
718242n0sk1llInside information (BOI21_servers)C++14
50 / 100
359 ms129228 KiB
#include <bits/stdc++.h> #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0) #define mp make_pair #define xx first #define yy second #define pb push_back #define pf push_front #define popb pop_back #define popf pop_front #define all(x) (x).begin(),(x).end() #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++) #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++) #define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--) #define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--) using namespace std; long double typedef ld; unsigned int typedef ui; long long int typedef li; pair<int,int> typedef pii; pair<li,li> typedef pli; pair<ld,ld> typedef pld; vector<vector<int>> typedef graph; unsigned long long int typedef ull; //const int mod = 998244353; const int mod = 1000000007; //Note to self: Check for overflow int n; int idx=0; bool val[44000007]; int L[44000007],R[44000007]; void add(int p, int q, int l, int r, int x) { if (l==x && x==r) val[p]=1; else if (l<=x && x<=r) { val[p]=1; int mid=(l+r)/2; if (x<=mid) R[p]=R[q],L[p]=++idx,add(L[p],L[q],l,mid,x); else L[p]=L[q],R[p]=++idx,add(R[p],R[q],mid+1,r,x); } } bool qry(int p, int l, int r, int s) { if (l==r) return val[p]; int mid=(l+r)/2; if (s<=mid) return qry(L[p],l,mid,s); else return qry(R[p],mid+1,r,s); } vector<int> svi; void dfs(int p, int l, int r) { if (!val[p]) return; if (l==r) svi.pb(l); else { int mid=(l+r)/2; dfs(L[p],l,mid); dfs(R[p],mid+1,r); } } int root[125005]; int siz[125005]; void spoji(int a, int b) { if (siz[a]>siz[b]) swap(a,b); dfs(root[a],1,n); int tmp; for (auto it : svi) tmp=++idx,add(tmp,root[b],1,n,it),root[b]=tmp; root[a]=tmp,root[b]=tmp,siz[b]+=siz[a],siz[a]=siz[b]; svi.clear(); } int main() { FAST; int q; cin>>n>>q; fff(i,1,n) root[i]=++idx,siz[i]=1; fff(i,1,n) { int tmp=++idx; add(tmp,root[i],1,n,i); root[i]=tmp; } q+=n-1; while (q--) { char t; cin>>t; if (t=='C') return cout<<"necu radim",0; if (t=='S') { int u,v; cin>>u>>v; spoji(u,v); } else //t=='Q' { int u,x; cin>>u>>x; cout<<(qry(root[u],1,n,x)?"yes":"no")<<"\n"; } } }

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:13:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
servers.cpp:92:5: note: in expansion of macro 'fff'
   92 |     fff(i,1,n) root[i]=++idx,siz[i]=1;
      |     ^~~
servers.cpp:13:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
servers.cpp:93:5: note: in expansion of macro 'fff'
   93 |     fff(i,1,n)
      |     ^~~
servers.cpp: In function 'void spoji(int, int)':
servers.cpp:83:12: warning: 'tmp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   83 |     root[a]=tmp,root[b]=tmp,siz[b]+=siz[a],siz[a]=siz[b];
      |     ~~~~~~~^~~~
#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...
#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...