Submission #535358
Source Code Expand
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
const int MAX_V=100000,LOGV=17,inf=1e9+7;
int N,Q,a[MAX_V];
int par[MAX_V][LOGV],depth[MAX_V],mx[MAX_V][LOGV];
vector<int> G[MAX_V];
void dfs(int v,int p){
if(p<0) depth[v]=0;
else depth[v]=depth[p]+1;
par[v][0]=p;
mx[v][0]=a[v];
for(int u:G[v]){
if(u!=p) dfs(u,v);
}
}
void genlca(){
dfs(0,-1);
for(int i=1;i<LOGV;i++){
rep(v,N){
if(par[v][i-1]==-1) par[v][i]=-1,mx[v][i]=inf;
else{
par[v][i]=par[par[v][i-1]][i-1];
mx[v][i]=min(mx[v][i-1],mx[par[v][i-1]][i-1]);
}
}
}
}
int lca(int u,int v){
if(depth[u]<depth[v]){
swap(u,v);
}
int d=depth[u]-depth[v];
rep(i,LOGV){
if((d>>i)&1) u=par[u][i];
}
if(u==v) return u;
for(int i=LOGV-1;i>=0;i--){
if(par[u][i]!=par[v][i]){
u=par[u][i];
v=par[v][i];
}
}
return par[v][0];
}
void up(int &u,int to,int& x){
for(int i=LOGV-1;i>=0;i--){
if(depth[u]-(1<<i)<depth[to]) continue;
if(mx[u][i]>x) u=par[u][i];
}
x%=a[u];
if(u!=to) u=par[u][0];
x%=a[u];
}
int downto(int u,int v,int d){
// u->v down dist d
int dist=depth[v]-depth[u];
if(dist<d) return -1;
int D=dist-d;
rep(i,LOGV) if((D>>i)&1) v=par[v][i];
return v;
}
void down(int &u,int to,int& x){
for(int i=LOGV-1;i>=0;i--){
int w=downto(u,to,(1<<i));
if(w==-1) continue;
if(mx[w][i]>x) u=w;
// printf("nxtu=%d\n",u);
}
x%=a[u];
if(u!=to) u=downto(u,to,1);
x%=a[u];
}
int main(){
cin>>N>>Q;
rep(i,N) cin>>a[i];
rep(i,N-1){
int x,y;
cin>>x>>y;
x--,y--;
G[x].pb(y);
G[y].pb(x);
}
genlca();
rep(tt,Q){
int x,u,v;
cin>>x>>u>>v;
u--,v--;
int L=lca(u,v);
// show(L);
while(u!=L){
up(u,L,x);
}
x%=a[L];
while(u!=v){
// show(u);
down(u,v,x);
}
// show(u);
x%=a[v];
cout<<x<<endl;
}
}
Submission Info
Submission Time |
|
Task |
J - MODクエリ |
User |
sigma425 |
Language |
C++11 (GCC 4.9.2) |
Score |
400 |
Code Size |
2148 Byte |
Status |
AC |
Exec Time |
1641 ms |
Memory |
25144 KB |
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 |
75 ms |
3188 KB |
15_path_00.txt |
AC |
31 ms |
3352 KB |
15_path_01.txt |
AC |
34 ms |
3300 KB |
15_path_02.txt |
AC |
32 ms |
3244 KB |
15_path_03.txt |
AC |
35 ms |
3204 KB |
15_path_04.txt |
AC |
31 ms |
3256 KB |
16_path_05.txt |
AC |
33 ms |
3436 KB |
16_path_06.txt |
AC |
32 ms |
3244 KB |
16_path_07.txt |
AC |
32 ms |
3252 KB |
16_path_08.txt |
AC |
33 ms |
3256 KB |
16_path_09.txt |
AC |
32 ms |
3344 KB |
17_path_10.txt |
AC |
1450 ms |
25132 KB |
17_path_11.txt |
AC |
1521 ms |
25144 KB |
17_path_12.txt |
AC |
1578 ms |
25072 KB |
17_path_13.txt |
AC |
1641 ms |
25144 KB |
17_path_14.txt |
AC |
1509 ms |
25132 KB |
20_random_15.txt |
AC |
32 ms |
3184 KB |
20_random_16.txt |
AC |
33 ms |
3280 KB |
20_random_17.txt |
AC |
33 ms |
3248 KB |
21_random_18.txt |
AC |
34 ms |
3240 KB |
21_random_19.txt |
AC |
33 ms |
3288 KB |
21_random_20.txt |
AC |
37 ms |
3352 KB |
30_random_21.txt |
AC |
38 ms |
3200 KB |
30_random_22.txt |
AC |
34 ms |
3244 KB |
30_random_23.txt |
AC |
33 ms |
3276 KB |
40_random_24.txt |
AC |
945 ms |
20460 KB |
40_random_25.txt |
AC |
994 ms |
20516 KB |
40_random_26.txt |
AC |
964 ms |
20528 KB |
49_sample_02.txt |
AC |
34 ms |
3272 KB |
61_test_27.txt |
AC |
1138 ms |
22640 KB |
61_test_28.txt |
AC |
1300 ms |
22712 KB |
61_test_29.txt |
AC |
1258 ms |
21900 KB |
63_star_30.txt |
AC |
833 ms |
20760 KB |
63_star_31.txt |
AC |
840 ms |
20768 KB |
63_star_32.txt |
AC |
904 ms |
20764 KB |
64_three_33.txt |
AC |
1527 ms |
23220 KB |
64_three_34.txt |
AC |
1409 ms |
23472 KB |
64_three_35.txt |
AC |
1408 ms |
22692 KB |