제출 #140748

#제출 시각아이디문제언어결과실행 시간메모리
140748rzbtBirthday gift (IZhO18_treearray)C++14
100 / 100
1652 ms84868 KiB
#include <bits/stdc++.h> #define mp make_pair #define pb push_back #define F first #define S second #define all(x) x.begin(),x.end() #define MAXN 200005 using namespace std; int n,m,q; vector<int> niz[MAXN]; int predak[MAXN][21]; int dubina[MAXN]; int a[MAXN]; set<int> s[MAXN],sp[MAXN]; void dfs(int t,int o,int h){ predak[t][0]=o; dubina[t]=h; for(auto x:niz[t]) if(x!=o) dfs(x,t,h+1); } int lca(int a, int b){ if(dubina[b]>dubina[a])swap(a,b); for(int j=20;j>=0;j--){ if(dubina[predak[a][j]]>=dubina[b])a=predak[a][j]; } if(a==b)return a; for(int j=20;j>=0;j--){ if(predak[a][j]!=predak[b][j]){ a=predak[a][j]; b=predak[b][j]; } } return predak[a][0]; } int main() { scanf("%d %d %d", &n, &m, &q); for(int i=1;i<n;i++){ int t1,t2; scanf("%d %d", &t1, &t2); niz[t1].pb(t2); niz[t2].pb(t1); } dfs(1,0,1); for(int j=1;j<21;j++) for(int i=1;i<=n;i++) predak[i][j]=predak[predak[i][j-1]][j-1]; for(int i=1;i<=m;i++) scanf("%d",a+i); for(int i=1;i<m;i++) s[lca(a[i],a[i+1])].insert(i); for(int i=1;i<=m;i++) sp[a[i]].insert(i); while(q--){ int qt; //FITTER HAPPIER MORE PRODUCTIVE scanf("%d", &qt); if(qt==1){ int pos,x; scanf("%d %d", &pos,&x); sp[a[pos]].erase(pos); if(pos>1)s[lca(a[pos],a[pos-1])].erase(pos-1); if(pos<m)s[lca(a[pos],a[pos+1])].erase(pos); a[pos]=x; sp[a[pos]].insert(pos); if(pos>1)s[lca(a[pos],a[pos-1])].insert(pos-1); if(pos<m)s[lca(a[pos],a[pos+1])].insert(pos); }else if(qt==2){ int l,r,x; scanf("%d %d %d", &l, &r, &x); //printf(" %d %d\n",sp[x].size(),s[x].size()); auto t1=sp[x].lower_bound(l); auto t2=s[x].lower_bound(l); //printf(" %d %d %d %d\n",sp[x].size(),s[x].size(),t1,t2); if(t1!=sp[x].end() && (*t1)<=r)printf("%d %d\n",*t1,*t1); else if(t2!=s[x].end() && (*t2)<r)printf("%d %d\n",*t2,(*t2)+1); else printf("-1 -1\n"); } else{ int x,y; scanf("%d %d", &x, &y); printf(" %d\n",lca(a[x],a[y])); } } return 0; }

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

treearray.cpp: In function 'int main()':
treearray.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &t1, &t2);
         ~~~~~^~~~~~~~~~~~~~~~~~~
treearray.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",a+i);
         ~~~~~^~~~~~~~~~
treearray.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &qt);
         ~~~~~^~~~~~~~~~~
treearray.cpp:68:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &pos,&x);
             ~~~~~^~~~~~~~~~~~~~~~~~
treearray.cpp:84:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d %d", &l, &r, &x);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:96:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...