Submission #551434


Source Code Expand

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

vector<int> G[100100];
int par[100100][20];
int dep[100100];
int vals[100100][20];
int N;

void dfs(int v,int p,int d){
	par[v][0]=p;
	dep[v]=d;
	for(int i=0;i<G[v].size();i++){
		int u=G[v][i];
		if(u==p) continue;
		dfs(u,v,d+1);
	}
}

void precalc(){
	for(int j=1;j<20;j++){
		for(int i=0;i<N;i++){
			if(par[i][j-1]==-1){
				par[i][j]=-1;
				vals[i][j]=-1;
			}else{
				par[i][j]=par[par[i][j-1]][j-1];
				vals[i][j]=min(vals[i][j-1],vals[par[i][j-1]][j-1]);
			}
		}
	}
}

int get_lca(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);
	int d=dep[u]-dep[v];
	for(int i=0;i<20;i++){
		if((d>>i)&1){
			u=par[u][i];
		}
	}
	if(u==v) return u;
	for(int i=19;i>=0;i--){
		if(par[u][i]!=par[v][i]){
			u=par[u][i];
			v=par[v][i];
		}
	}
	return par[u][0];
}

int get_ancestor(int v,int dis){
	for(int i=0;i<20;i++){
		if((dis>>i)&1){
			v=par[v][i];
		}
	}
	return v;
}

int get_nxt_up(int v,int lca,int x){
	//already divided in v
	//v != lca
	if(x==0) return lca;
	for(int i=19;i>=0;i--){
		if(dep[v]-dep[lca]<(1<<i)) continue;
		if(vals[v][i]<=x) continue;
		return par[v][i];
	}
	fprintf(stderr,"error get_nxt_up %d %d %d\n",v,lca,x);
	return -1;
}

int get_nxt_down(int from,int to,int x){
	//already divided in from
	//from != to
	if(x==0) return to;
	int dis=dep[to]-dep[from];
	for(int i=19;i>=0;i--){
		int d=dis-(1<<i);
		if(d<0) continue;
		int nv=get_ancestor(to,d);
		int tmp=par[nv][0];
		int m=vals[tmp][i];
		if(m<=x) continue;
		return nv;
	}
	fprintf(stderr,"error get_nxt_down %d %d %d\n",from,to,x);
	return -1;
}

int go_up(int from,int to,int x){
	if(from==to){
		return x%vals[from][0];
	}
	while(from!=to){
		x%=vals[from][0];
		int nv=get_nxt_up(from,to,x);
		from=nv;
	}
	return x%vals[to][0];
}

int go_down(int from,int to,int x){
	if(from==to){
		return x%vals[from][0];
	}
	while(from!=to){
		x%=vals[from][0];
		int nv=get_nxt_down(from,to,x);
		from=nv;
		//printf("%d %d\n",from,x);
	}
	return x%vals[to][0];
}

int solve(int u,int v,int x){
	int lca=get_lca(u,v);
	x=go_up(u,lca,x);
	x=go_down(lca,v,x);
	return x;
}

int main(){
	int Q;
	scanf("%d%d",&N,&Q);
	for(int i=0;i<N;i++){
		scanf("%d",&vals[i][0]);
	}
	for(int i=0;i<N-1;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		u--;v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(0,-1,0);
	precalc();
	for(int q=0;q<Q;q++){
		int x,u,v;
		scanf("%d%d%d",&x,&u,&v);
		u--;v--;
		int ans=solve(u,v,x);
		printf("%d\n",ans);
	}
	return 0;
}

Submission Info

Submission Time
Task J - MODクエリ
User wo01
Language C++ (GCC 4.9.2)
Score 400
Code Size 2650 Byte
Status AC
Exec Time 912 ms
Memory 26976 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:129:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&N,&Q);
                     ^
./Main.cpp:131:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&vals[i][0]);
                          ^
./Main.cpp:135:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&u,&v);
                      ^
./Main.cpp:144:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&x,&u,&v);
                           ^

Judge Result

Set Name Small All
Score / Max Score 30 / 30 370 / 370
Status
AC × 16
AC × 38
Set Name Test Cases
Small 00_sample_path_01.txt, 15_path_00.txt, 15_path_01.txt, 15_path_02.txt, 15_path_03.txt, 15_path_04.txt, 16_path_05.txt, 16_path_06.txt, 16_path_07.txt, 16_path_08.txt, 16_path_09.txt, 17_path_10.txt, 17_path_11.txt, 17_path_12.txt, 17_path_13.txt, 17_path_14.txt
All 00_sample_path_01.txt, 15_path_00.txt, 15_path_01.txt, 15_path_02.txt, 15_path_03.txt, 15_path_04.txt, 16_path_05.txt, 16_path_06.txt, 16_path_07.txt, 16_path_08.txt, 16_path_09.txt, 17_path_10.txt, 17_path_11.txt, 17_path_12.txt, 17_path_13.txt, 17_path_14.txt, 20_random_15.txt, 20_random_16.txt, 20_random_17.txt, 21_random_18.txt, 21_random_19.txt, 21_random_20.txt, 30_random_21.txt, 30_random_22.txt, 30_random_23.txt, 40_random_24.txt, 40_random_25.txt, 40_random_26.txt, 49_sample_02.txt, 61_test_27.txt, 61_test_28.txt, 61_test_29.txt, 63_star_30.txt, 63_star_31.txt, 63_star_32.txt, 64_three_33.txt, 64_three_34.txt, 64_three_35.txt
Case Name Status Exec Time Memory
00_sample_path_01.txt AC 32 ms 3036 KB
15_path_00.txt AC 34 ms 3104 KB
15_path_01.txt AC 31 ms 3092 KB
15_path_02.txt AC 28 ms 3108 KB
15_path_03.txt AC 28 ms 3104 KB
15_path_04.txt AC 30 ms 3104 KB
16_path_05.txt AC 30 ms 3104 KB
16_path_06.txt AC 30 ms 3108 KB
16_path_07.txt AC 29 ms 3108 KB
16_path_08.txt AC 29 ms 3112 KB
16_path_09.txt AC 28 ms 3112 KB
17_path_10.txt AC 910 ms 26924 KB
17_path_11.txt AC 866 ms 26916 KB
17_path_12.txt AC 861 ms 26908 KB
17_path_13.txt AC 912 ms 26976 KB
17_path_14.txt AC 892 ms 26916 KB
20_random_15.txt AC 30 ms 3112 KB
20_random_16.txt AC 30 ms 3104 KB
20_random_17.txt AC 28 ms 3232 KB
21_random_18.txt AC 34 ms 3228 KB
21_random_19.txt AC 32 ms 3096 KB
21_random_20.txt AC 30 ms 3100 KB
30_random_21.txt AC 32 ms 3228 KB
30_random_22.txt AC 30 ms 3228 KB
30_random_23.txt AC 31 ms 3108 KB
40_random_24.txt AC 385 ms 22304 KB
40_random_25.txt AC 379 ms 22308 KB
40_random_26.txt AC 364 ms 22300 KB
49_sample_02.txt AC 31 ms 3104 KB
61_test_27.txt AC 685 ms 24488 KB
61_test_28.txt AC 670 ms 24480 KB
61_test_29.txt AC 602 ms 23584 KB
63_star_30.txt AC 280 ms 22672 KB
63_star_31.txt AC 293 ms 22684 KB
63_star_32.txt AC 300 ms 22684 KB
64_three_33.txt AC 702 ms 24972 KB
64_three_34.txt AC 661 ms 25376 KB
64_three_35.txt AC 625 ms 24608 KB