제출 #260628

#제출 시각아이디문제언어결과실행 시간메모리
260628uacoder123Birthday gift (IZhO18_treearray)C++14
0 / 100
9 ms14464 KiB
#include <bits/stdc++.h> using namespace std; #define F first #define S second #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i) #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i) #define all(x) (x).begin(), (x).end() #define sz(x) lli(x.size()) #define mp(i,a) make_pair(i,a) #define pb(a) push_back(a) #define bit(x,b) (x&(1LL<<b)) typedef long long int lli; typedef pair <lli,lli> ii; typedef pair <lli,ii> iii; typedef vector <lli> vi; vi al[200001]; set<ii> ans[200001]; int par[200001][32],din[200001],dout[200001],ti=0,n,m,q,arr[200001]; void dfs(int node,int p) { par[node][0]=p; for(int i=1;i<32;++i) par[node][i]=par[par[node][i-1]][i-1]; din[node]=ti++; for(int i=0;i<al[node].size();++i) if(al[node][i]!=p) dfs(al[node][i],node); dout[node]=ti++; } bool isa(int f,int s) { return (din[f]<=din[s])&&(dout[f]>=dout[s]); } int lca(int f,int s) { if(isa(f,s)) return f; if(isa(s,f)) return s; for(int i=31;i>=0;--i) if(!isa(par[f][i],s)) f=par[f][i]; return par[f][0]; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n>>m>>q; for(int i=0;i<n-1;++i) { int f,s; cin>>f>>s; al[f].pb(s); al[s].pb(f); } dfs(1,1); for(int i=0;i<m;++i) cin>>arr[i]; for(int i=0;i<m;++i) { ans[arr[m]].insert(mp(i,i)); int l; if(i!=0) { l=lca(arr[i-1],arr[i]); ans[l].insert(mp(i-1,i)); } if(i!=m-1) { l=lca(arr[i+1],arr[i]); ans[l].insert(mp(i,i+1)); } } for(int i=0;i<q;++i) { int t,f,s,l,v; cin>>t>>f>>s; if(t==1) { f--; ans[arr[f]].erase(mp(f,f)); if(f!=0) { l=lca(arr[f-1],arr[f]); ans[l].erase(mp(f-1,f)); } if(f!=m-1) { l=lca(arr[f+1],arr[f]); ans[l].erase(mp(f,f+1)); } arr[f]=s; ans[s].insert(mp(f,f)); if(f!=0) { l=lca(arr[f-1],arr[f]); ans[l].insert(mp(f-1,f)); } if(f!=m-1) { l=lca(arr[f+1],arr[f]); ans[l].insert(mp(f,f+1)); } } else { f--; s--; cin>>v; auto it=ans[v].lower_bound(mp(f,0)); if(it!=ans[v].end()) { if((*it).S<=s) cout<<(*it).F+1<<' '<<(*it).S+1<<endl; else cout<<-1<<' '<<-1<<endl; } else cout<<-1<<' '<<-1<<endl; } } return(0); }

컴파일 시 표준 에러 (stderr) 메시지

treearray.cpp: In function 'void dfs(int, int)':
treearray.cpp:26:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<al[node].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...