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 |
|
|
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 |