This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |