京都大学プログラミングコンテスト2015

Submission #534864

Source codeソースコード

#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };
 
ll MOD = 1000000007;
ll _MOD = 1000000009;
int INF = INT_MAX / 3;
double EPS = 1e-10;

vector<int> G[100000];
int parent[20][100000], mi[20][100000];
int a[100000], depth[100000];
 
void dfs(int v, int p, int d) {
	parent[0][v] = p;
	mi[0][v] = a[v];
	depth[v] = d;
	for (int i = 0; i < G[v].size(); i++)
		if (G[v][i] != p) dfs(G[v][i], v, d + 1);
}
 
void init(int V) {
	dfs(0, -1, 0);
	for (int k = 0; k + 1 < 20; k++)
		for (int v = 0; v < V; v++) {
			if (parent[k][v] < 0) parent[k + 1][v] = -1;
			else parent[k + 1][v] = parent[k][parent[k][v]];
			mi[k + 1][v] = mi[k][v];
			if (parent[k][v] != -1) 
				mi[k + 1][v] = min(mi[k + 1][v], mi[k][parent[k][v]]);
		}
}
 
int lca(int u, int v) {
	if (depth[u] > depth[v]) swap(u, v);
	for (int k = 0; k < 20; k++)
		if ((depth[v] - depth[u]) >> k & 1)
			v = parent[k][v];
	if (u == v) return u;
	for (int k = 20 - 1; k >= 0; k--)
		if (parent[k][u] != parent[k][v]) {
			u = parent[k][u];
			v = parent[k][v];
		}
	return parent[0][u];
}

int f(int x, int z) {
	int ans = INT_MAX;
	for (int k = 19; k >= 0; k--)
		if (parent[k][x] != -1 && depth[parent[k][x]] >= depth[z]) {
			ans = min(ans, mi[k][x]);
			x = parent[k][x];
		}
	return ans;
}

int main() {
	int N, Q; cin >> N >> Q;
	for (int u = 0; u < N; u++)
		scanf("%d", &a[u]);
	for (int i = 0; i < N - 1; i++) {
		int b, c; scanf("%d%d", &b, &c);
		b--; c--;
		G[b].push_back(c);
		G[c].push_back(b);
	}
	init(N);
	while (Q--) {
		int q, x, y; scanf("%d%d%d", &q, &x, &y);
		x--; y--;
		int z = lca(x, y);
		while (q && x != z) {
			q %= a[x];
			for (int k = 19; k >= 0; k--)
				if (parent[k][x] != -1 && depth[parent[k][x]] >= depth[z] && mi[k][x] > q)
					x = parent[k][x];
			//x = parent[0][x];
		}
		q %= a[z];
		//cout << "q=" << q << endl;
		while (q && x != y) {
			//cout << x << ' ' << q << endl;
			q %= a[x];
			int _y = y;
			for (int k = 19; k >= 0; k--) {
				if (parent[k][_y] == -1 || depth[parent[k][_y]] <= depth[z]) continue;
				if (f(parent[k][_y], z) <= q) _y = parent[k][_y];
			}
			x = _y;
		}
		q %= a[y];
		printf("%d\n", q);
	}
}

Submission

Task問題 J - MODクエリ
User nameユーザ名 sugim48
Created time投稿日時
Language言語 C++11 (GCC 4.9.2)
Status状態 AC
Score得点 400
Source lengthソースコード長 2812 Byte
File nameファイル名
Exec time実行時間 1160 ms
Memory usageメモリ使用量 27432 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:87:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[u]);
^
./Main.cpp:89:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int b, c; scanf("%d%d", &b, &c);
^
./Main.cpp:96:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int q, x, y; scanf("%d%d%d", &q, &x, &y);
^

Test case

Set

Set name Score得点 / Max score Cases
Small 30 / 30 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 370 / 370 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_sample_path_01.txt AC 45 ms 3372 KB
15_path_00.txt AC 48 ms 3360 KB
15_path_01.txt AC 41 ms 3424 KB
15_path_02.txt AC 32 ms 3356 KB
15_path_03.txt AC 31 ms 3364 KB
15_path_04.txt AC 31 ms 3364 KB
16_path_05.txt AC 31 ms 3336 KB
16_path_06.txt AC 31 ms 3356 KB
16_path_07.txt AC 33 ms 3360 KB
16_path_08.txt AC 33 ms 3360 KB
16_path_09.txt AC 31 ms 3368 KB
17_path_10.txt AC 1124 ms 27396 KB
17_path_11.txt AC 1091 ms 27304 KB
17_path_12.txt AC 1084 ms 27400 KB
17_path_13.txt AC 1106 ms 27432 KB
17_path_14.txt AC 1111 ms 27420 KB
20_random_15.txt AC 32 ms 3356 KB
20_random_16.txt AC 54 ms 3280 KB
20_random_17.txt AC 32 ms 3352 KB
21_random_18.txt AC 33 ms 3344 KB
21_random_19.txt AC 31 ms 3368 KB
21_random_20.txt AC 32 ms 3372 KB
30_random_21.txt AC 33 ms 3364 KB
30_random_22.txt AC 33 ms 3356 KB
30_random_23.txt AC 31 ms 3356 KB
40_random_24.txt AC 529 ms 22752 KB
40_random_25.txt AC 533 ms 22824 KB
40_random_26.txt AC 517 ms 22812 KB
49_sample_02.txt AC 31 ms 3348 KB
61_test_27.txt AC 1160 ms 24964 KB
61_test_28.txt AC 1107 ms 24992 KB
61_test_29.txt AC 1024 ms 24068 KB
63_star_30.txt AC 276 ms 23036 KB
63_star_31.txt AC 280 ms 23064 KB
63_star_32.txt AC 278 ms 23204 KB
64_three_33.txt AC 1053 ms 25380 KB
64_three_34.txt AC 1041 ms 25760 KB
64_three_35.txt AC 1009 ms 24992 KB