oj.uz

답안 #89101

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
89101 2018-12-10T10:06:22 Z nika 특수한 그래프 (IZhO13_specialg) C++14
100 / 100
 330 ms 42408 KB 
#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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 3064 KB Output is correct
2 Correct 8 ms 3484 KB Output is correct
3 Correct 8 ms 3484 KB Output is correct
4 Correct 16 ms 3484 KB Output is correct
5 Correct 8 ms 3484 KB Output is correct
6 Correct 23 ms 3880 KB Output is correct
7 Correct 23 ms 4044 KB Output is correct
8 Correct 23 ms 4160 KB Output is correct
9 Correct 23 ms 4160 KB Output is correct
10 Correct 23 ms 4160 KB Output is correct
11 Correct 285 ms 25508 KB Output is correct
12 Correct 176 ms 25508 KB Output is correct
13 Correct 237 ms 25508 KB Output is correct
14 Correct 204 ms 25508 KB Output is correct
15 Correct 221 ms 25508 KB Output is correct
16 Correct 233 ms 25516 KB Output is correct
17 Correct 280 ms 34852 KB Output is correct
18 Correct 232 ms 36612 KB Output is correct
19 Correct 282 ms 38792 KB Output is correct
20 Correct 330 ms 42408 KB Output is correct