Submission #534864

---

Source Code Expand

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

Compile Error

./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);
                                           ^

Judge Result