oj.uz

답안 #82324

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
82324 2018-10-29T23:56:00 Z _ypc 특수한 그래프 (IZhO13_specialg) C++
100 / 100
 272 ms 43676 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 9 ms 2940 KB Output is correct
2 Correct 8 ms 3324 KB Output is correct
3 Correct 8 ms 3324 KB Output is correct
4 Correct 15 ms 3324 KB Output is correct
5 Correct 9 ms 3376 KB Output is correct
6 Correct 25 ms 3680 KB Output is correct
7 Correct 26 ms 3884 KB Output is correct
8 Correct 27 ms 4204 KB Output is correct
9 Correct 28 ms 4380 KB Output is correct
10 Correct 25 ms 4744 KB Output is correct
11 Correct 268 ms 26736 KB Output is correct
12 Correct 180 ms 26736 KB Output is correct
13 Correct 258 ms 26736 KB Output is correct
14 Correct 148 ms 26736 KB Output is correct
15 Correct 170 ms 26736 KB Output is correct
16 Correct 170 ms 26736 KB Output is correct
17 Correct 231 ms 35884 KB Output is correct
18 Correct 222 ms 37904 KB Output is correct
19 Correct 222 ms 39908 KB Output is correct
20 Correct 272 ms 43676 KB Output is correct