Submission #89101

#	Time	Username	Problem	Language	Result	Execution time	Memory
89101		nika	Special graph (IZhO13_specialg)	C++14	100 / 100	330 ms	42408 KiB

specialg

#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);
    ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 100 / 100