Submission #82324

#TimeUsernameProblemLanguageResultExecution timeMemory
82324_ypcSpecial graph (IZhO13_specialg)C++98
100 / 100
272 ms43676 KiB
#include<stdio.h> #include<vector> #define M 100010 using namespace std; vector<int>con[M]; int val,sw,m,pos[M],k,anc,s1,s2,lev[M],t=1,n,ch[M],a[M],root[M],w,s[M],e[M],cnt,d[21][M]; struct data{ int x,ch; }tree[M*5]; void dfs(int x){ if(ch[x]) return; ch[x]=k; if(ch[a[x]]==k || a[x]==0){root[++w]=x; return;} con[a[x]].push_back(x); dfs(a[x]); } void dfs2(int x,int h){ s[x]=++cnt; lev[x]=h; for(int i=0;i<con[x].size();i++) dfs2(con[x][i],h+1); e[x]=cnt; } int update(int x,int y,int k,int s,int e,int p){ if(tree[k].ch){ tree[k].x=max(tree[k].x,tree[k].ch); tree[k*2].ch=max(tree[k*2].ch,tree[k].ch); tree[k*2+1].ch=max(tree[k*2+1].ch,tree[k].ch); tree[k].ch=0; } if(s<=x && y<=e){ tree[k].x=max(tree[k].x,p); tree[k*2].ch=max(tree[k*2].ch,p); tree[k*2+1].ch=max(tree[k*2+1].ch,p); return tree[k].x; } if(s>y || e<x) return 0; return tree[k].x=max(update(x,(x+y)/2,k*2,s,e,p),update((x+y)/2+1,y,k*2+1,s,e,p)); } int LCA(int x,int c){ int i; for(i=0;i<=17;i++){ if((1<<i)&c) x=d[i][x]; } return x; } void check(int x,int y){ int p; p=LCA(x,lev[x]-lev[y]); if(p!=y) return; s1=update(1,t,1,s[x],s[x],0); s2=update(1,t,1,s[y],s[y],0); if(s1==s2){printf("%d\n",lev[x]-lev[y]+val); sw=1;} } void pro2(int x,int y){ sw=0; if(lev[x]>=lev[y]){val=0; check(x,y);} if(sw==0){ s1=update(1,t,1,s[x],s[x],0); val=lev[x]; anc=LCA(x,lev[x]-1); if(s1==0) x=a[anc]; if(lev[x]<lev[y]){printf("-1\n"); return;} check(x,y); if(sw==0) printf("-1\n"); } } int main(){ int i,j,x,y,z; scanf("%d",&n); for(;;){if(t>=n) break; t*=2;} for(i=1;i<=n;i++){ scanf("%d",&a[i]); d[0][i]=a[i]; } for(i=1;i<=n;i++){k++; dfs(i);} for(i=1;i<=w;i++){ d[0][root[i]]=0; dfs2(root[i],1); } for(i=1;i<=17;i++){ for(j=1;j<=n;j++){ d[i][j]=d[i-1][d[i-1][j]]; } } scanf("%d",&m); for(i=1;i<=m;i++){ scanf("%d",&x); if(x==1){ scanf("%d",&y); update(1,t,1,s[y],e[y],s[y]); } else{ scanf("%d %d",&y,&z); pro2(y,z); } } return 0; }

Compilation message (stderr)

specialg.cpp: In function 'void dfs2(int, int)':
specialg.cpp:19:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<con[x].size();i++) dfs2(con[x][i],h+1);
                 ~^~~~~~~~~~~~~~
specialg.cpp: In function 'int main()':
specialg.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
specialg.cpp:70:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d",&a[i]);
      ~~~~~^~~~~~~~~~~~
specialg.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
  ~~~~~^~~~~~~~~
specialg.cpp:85:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d",&x);
      ~~~~~^~~~~~~~~
specialg.cpp:87:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&y);
    ~~~~~^~~~~~~~~
specialg.cpp:91:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&y,&z);
    ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...