Submission #534024
Source Code Expand
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
using namespace std;
#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
int N;
int a[100010];
vector <int> graph[100010];
int depth[100010];
int parent[100010][30];
int parentmin[100010][30];
void dfs(int p, int x, int d){
int i;
parent[x][0] = p;
depth[x] = d;
REP(i,graph[x].size()){
int y = graph[x][i];
if(y != p) dfs(x, y, d+1);
}
}
void pre(void){
int i,j,d;
REP(i,N) parentmin[i][0] = a[i];
for(d=1;d<20;d++) REP(i,N){
int x = i;
int y = parent[x][d-1];
if(y == -1){
parent[x][d] = -1;
parentmin[x][d] = parentmin[x][d-1];
} else {
parent[x][d] = parent[y][d-1];
parentmin[x][d] = min(parentmin[x][d-1], parentmin[y][d-1]);
}
}
}
int query_up(int val, int s, int d){
int i;
if(d == 0) return val;
if(a[s] <= val) return query_up(val % a[s], parent[s][0], d-1);
for(i=16;i>=0;i--) if((1<<i) <= d && parentmin[s][i] > val) return query_up(val, parent[s][i], d - (1<<i));
return -1;
}
int query_down(int val, int s, int d){
int i;
if(d == 0) return val;
if(d == 1) return val % a[s];
for(i=16;i>=0;i--) if((1<<i) <= d) break;
if((1<<i) < d){
int tmp = query_down(val, parent[s][i], d - (1<<i));
return query_down(tmp, s, (1<<i));
}
if(parentmin[s][i] > val) return val;
i--;
int tmp2 = query_down(val, parent[s][i], d - (1<<i));
return query_down(tmp2, s, (1<<i));
}
int query(int x, int s, int t){
int i;
int ds = 0, dt = 0;
int ss = s, tt = t;
for(i=16;i>=0;i--) if(depth[ss] - (1<<i) >= depth[tt]){
ss = parent[ss][i];
ds += (1<<i);
}
for(i=16;i>=0;i--) if(depth[tt] - (1<<i) >= depth[ss]){
tt = parent[tt][i];
dt += (1<<i);
}
int lca = ss;
if(ss != tt){
for(i=16;i>=0;i--) if(parent[ss][i] != parent[tt][i]){
ss = parent[ss][i];
tt = parent[tt][i];
ds += (1<<i);
dt += (1<<i);
}
ds++;
dt++;
lca = parent[ss][0];
}
// cout << x << ' ' << s << ' ' << t << ' ' << ' ' << lca << ' ' << ds << ' ' << dt << endl;
int y = query_up(x, s, ds);
int z = query_down(y % a[lca], t, dt);
return z;
}
int main(void){
int Q,i;
cin >> N >> Q;
REP(i,N) scanf("%d", &a[i]);
REP(i,N-1){
int b,c;
scanf("%d%d", &b, &c);
b--; c--;
graph[b].push_back(c);
graph[c].push_back(b);
}
dfs(-1, 0, 0);
pre();
REP(i,Q){
int x,s,t;
scanf("%d%d%d", &x, &s, &t);
int ans = query(x, s-1, t-1);
printf("%d\n", ans);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
J - MODクエリ |
User |
takahashikun |
Language |
C++ (GCC 4.9.2) |
Score |
400 |
Code Size |
2927 Byte |
Status |
AC |
Exec Time |
546 ms |
Memory |
35196 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:128:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
REP(i,N) scanf("%d", &a[i]);
^
./Main.cpp:131:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &b, &c);
^
./Main.cpp:142:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &x, &s, &t);
^
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 |
36 ms |
3172 KB |
15_path_00.txt |
AC |
31 ms |
3112 KB |
15_path_01.txt |
AC |
28 ms |
3112 KB |
15_path_02.txt |
AC |
31 ms |
3096 KB |
15_path_03.txt |
AC |
28 ms |
3108 KB |
15_path_04.txt |
AC |
30 ms |
3040 KB |
16_path_05.txt |
AC |
28 ms |
3232 KB |
16_path_06.txt |
AC |
34 ms |
3096 KB |
16_path_07.txt |
AC |
31 ms |
3112 KB |
16_path_08.txt |
AC |
31 ms |
3108 KB |
16_path_09.txt |
AC |
30 ms |
3228 KB |
17_path_10.txt |
AC |
457 ms |
35196 KB |
17_path_11.txt |
AC |
448 ms |
35104 KB |
17_path_12.txt |
AC |
455 ms |
35108 KB |
17_path_13.txt |
AC |
474 ms |
35108 KB |
17_path_14.txt |
AC |
466 ms |
35100 KB |
20_random_15.txt |
AC |
30 ms |
3108 KB |
20_random_16.txt |
AC |
31 ms |
3104 KB |
20_random_17.txt |
AC |
29 ms |
3096 KB |
21_random_18.txt |
AC |
29 ms |
3104 KB |
21_random_19.txt |
AC |
33 ms |
3112 KB |
21_random_20.txt |
AC |
32 ms |
3228 KB |
30_random_21.txt |
AC |
30 ms |
3104 KB |
30_random_22.txt |
AC |
29 ms |
3104 KB |
30_random_23.txt |
AC |
33 ms |
3100 KB |
40_random_24.txt |
AC |
377 ms |
30500 KB |
40_random_25.txt |
AC |
378 ms |
30496 KB |
40_random_26.txt |
AC |
367 ms |
30492 KB |
49_sample_02.txt |
AC |
28 ms |
3228 KB |
61_test_27.txt |
AC |
483 ms |
32676 KB |
61_test_28.txt |
AC |
475 ms |
32676 KB |
61_test_29.txt |
AC |
487 ms |
31896 KB |
63_star_30.txt |
AC |
277 ms |
30872 KB |
63_star_31.txt |
AC |
279 ms |
30872 KB |
63_star_32.txt |
AC |
293 ms |
30868 KB |
64_three_33.txt |
AC |
546 ms |
33192 KB |
64_three_34.txt |
AC |
507 ms |
33564 KB |
64_three_35.txt |
AC |
533 ms |
32800 KB |