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