Submission #90710

#TimeUsernameProblemLanguageResultExecution timeMemory
90710janchomathBirthday gift (IZhO18_treearray)C++14
0 / 100
67 ms66548 KiB
#include<bits/stdc++.h> #define ll long long #define f first #define s second #define pb push_back using namespace std; ll in[200020],l,r,n,m,xx,yy,q,a[200020],type,pa; ll out[200020]; ll timer=1; ll P[200020][18]; ll lvl[200020]; ll indx[2000000]; vector<ll>v[200005],g; void dfs(int p,int u) { P[u][0]=p; for (int i=1;i<=17;i++) P[u][i]=P[P[u][i-1]][i-1]; timer++; in[u]=timer; indx[in[u]] = u; for (int i=0;i<v[u].size();i++) if (v[u][i] != p){ lvl[v[u][i]]=lvl[u]+1; dfs(u,v[u][i]); } out[u]=timer; } int lca(int a,int b) { if (in[a] <= in[b] && out[b] <= out[a]) return a; for (int i=17;i>=0;i--) if (P[a][i]) if (!(in[P[a][i]] <= in[b] && out[b] <= out[P[a][i]])) a=P[a][i]; return P[a][0]; } set<ll>st[200005],st1[200005],st2[200005]; int main(){ cin >> n >> m >> q; for(int i=1; i<n; i++){ cin >> xx >> yy; v[xx].pb(yy); v[yy].pb(xx); } dfs(1,1); for(int i=1; i<=m; i++){ cin >> a[i]; } for(int i=1; i<=m; i++){ xx = i; yy = a[i]; st[yy].insert(xx); if(xx != 1){ ll pp = lca(a[xx],a[xx-1]); pp = lca(yy,a[xx-1]); st1[pp].insert(xx); } if(xx != m){ ll pp = lca(a[xx],a[xx+1]); pp = lca(yy,a[xx+1]); st2[pp].insert(xx+1); } a[xx] = yy; } while(q--){ cin >> type; if(type == 1){ cin >> xx >> yy; st[a[xx]].erase(st[a[xx]].find(xx)); st[yy].insert(xx); if(xx != 1){ ll pp = lca(a[xx],a[xx-1]); st1[pp].erase(st1[pp].find(xx)); pp = lca(yy,a[xx-1]); st1[pp].insert(xx); } if(xx != m){ ll pp = lca(a[xx],a[xx+1]); st2[pp].erase(st2[pp].find(xx)); pp = lca(yy,a[xx+1]); st2[pp].insert(xx+1); } a[xx] = yy; } else { cin >> l >> r >> pa; if(st[pa].lower_bound(l) != st[pa].end()){ if(*(st[pa].lower_bound(l)) <= r){ cout << *(st[pa].lower_bound(l)) << " " << *(st[pa].lower_bound(l)) << endl; continue; } } if(st1[pa].lower_bound(l+1) != st1[pa].end()){ if(*(st1[pa].lower_bound(l+1)) <= r){ cout << *(st1[pa].lower_bound(l+1)) - 1<< " " << *(st1[pa].lower_bound(l+1)) << endl; continue; } } if(st2[pa].lower_bound(l) != st2[pa].end()){ if(*(st2[pa].lower_bound(l)) < r){ cout << *(st2[pa].lower_bound(l))<< " " << *(st2[pa].lower_bound(l)) + 1<< endl; continue; } } cout <<"-1 -1\n"; } } return 0; }

Compilation message (stderr)

treearray.cpp: In function 'void dfs(int, int)':
treearray.cpp:23:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[u].size();i++)
                  ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...