Submission #732326

---

Source Code Expand

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <functional>
#include <numeric>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <bitset>
#include <map>
#include <set>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

int n, q, a[100005];
int par[17][100005], pmin[17][100005], dep[100005];
vector<int> gph[100005];

void dfs(int x, int p){
	par[0][x] = p;
	pmin[0][x] = a[x];
	for(int i=1; i<17; i++){
		par[i][x] = par[i-1][par[i-1][x]];
		pmin[i][x] = min(pmin[i-1][x], pmin[i-1][par[i-1][x]]);
	}
	for(auto &i : gph[x]){
		if(i != p){
			dep[i] = dep[x] + 1;
			dfs(i, x);
		}
	}
}

int path_query(int s, int e){
	int dx = dep[e] - dep[s] + 1;
	int ret = 2e9;
	for(int i=0; i<=16; i++){
		if((dx >> i) & 1) {
			ret = min(ret, pmin[i][e]);
			e = par[i][e];
		}
	}
	return ret;
}

int level_ancestor(int x, int p){
	for(int i=0; i<=16; i++){
		if((p >> i) & 1) x = par[i][x];
	}
	return x;
}

int lca(int s, int e){
	if(dep[e] < dep[s]) swap(s, e);
	e = level_ancestor(e, dep[e] - dep[s]);
	for(int i=16; i>=0; i--){
		if(par[i][s] != par[i][e]){
			s = par[i][s];
			e = par[i][e];
		}
	}
	if(s != e) return par[0][s];
	return s;
}

int lowpath(int s, int e, int x){
	int st = 0, ed = dep[e] - dep[s];
	while(st != ed){
		int m = (st+ed)/ 2;
		if(path_query(level_ancestor(e, m), e) <= x){
			ed = m;
		}
		else st = m+1;
	}
	if(path_query(level_ancestor(e, st), e) > x) return -1;
	return level_ancestor(e, st);
}

int highpath(int s, int e, int x){
	int st = 0, ed = dep[e] - dep[s];
	while(st != ed){
		int m = (st+ed+1)/ 2;
		if(path_query(s, level_ancestor(e, m)) <= x){
			st = m;
		}
		else ed = m-1;
	}
	if(path_query(s, level_ancestor(e, st)) > x) return -1;
	return level_ancestor(e, st);
}

int main(){
	scanf("%d %d",&n,&q);
	for(int i=1; i<=n; i++){
		scanf("%d",&a[i]);
	}
	memset(pmin ,0x3f, sizeof(pmin));
	for(int i=0; i<n-1; i++){
		int s, e;
		scanf("%d %d",&s,&e);
		gph[s].push_back(e);
		gph[e].push_back(s);
	}
	dep[1] = 1;
	dfs(1, 0);
	for(int i=0; i<q; i++){
		int s, e, x;
		scanf("%d %d %d",&x,&s,&e);
		int l = lca(s, e);
		while(1){
			int p = lowpath(l, s, x);
			if(p == -1) break;
			x %= a[p];
		}
		while(1){
			int p = highpath(l, e, x);
			if(p == -1) break;
			x %= a[p];
		}
		printf("%d\n",x);
	}
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:103:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&q);
                      ^
./Main.cpp:105:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^
./Main.cpp:110:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&s,&e);
                       ^
./Main.cpp:118:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&x,&s,&e);
                             ^

Judge Result