Submission #1225217

---

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 <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
#include <random>
#include <unordered_set>
#include <complex>
using namespace std;

#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back

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; };
// typedef complex<double> C;

const int MOD = 1e9 + 7;
const int _MOD = 1000000009;
const int INF = INT_MAX / 2;
double EPS = 1e-10;

template <class Monoid>
struct segtree {
	using T = typename Monoid::T;
	int N;
	vector<T> a;
	segtree(const vector<T> &a0) {
		for (N = 1; N < a0.size(); N<<=1);
		a.resize(N<<1);
		copy(a0.begin(), a0.end(), a.begin() + N);
		for (int i = N - 1; i; i--)
			a[i] = Monoid::op(a[i<<1], a[i<<1 | 1]);
	}
	segtree(int N, const T &x = Monoid::id()) :
		segtree(vector<T>(N, x)) {}
	T get(int l, int r) {
		T xl = Monoid::id(), xr = Monoid::id();
		for (l += N, r += N; l < r; l>>=1, r>>=1) {
			if (l & 1) xl = Monoid::op(xl, a[l++]);
			if (r & 1) xr = Monoid::op(a[--r], xr);
		}
		return Monoid::op(xl, xr);
	}
	void set(int i, const T &x) {
		a[i += N] = x;
		while (i>>=1) a[i] = Monoid::op(a[i<<1], a[i<<1 | 1]);
	}
};

struct monoid {
	using T = int;
	static T id() { return 0; }
	static T op(const T &l, const T &r) { return l + r; }
};

void dfs_h(int u, vector<vector<int> >& G, vector<int>& l, vector<int>& h, vector<int>& ma) {
	h[u] += l[u];
	ma[u] = h[u];
	for (int v: G[u]) {
		h[v] = h[u];
		dfs_h(v, G, l, h, ma);
		ma[u] = max(ma[u], ma[v]);
	}
}

void dfs_ans(int u, vector<vector<int> >& G, vector<int>& h, vector<int>& ma, vector<int>& H, segtree<monoid>& st, map<int, int>& ans) {
	for (int v: G[u]) {
		int i = ma[v];
		st.set(i, st.get(i, i + 1) + 1);
	}
	int i = h[u], x = H[i];
	ans[x] = min(ans[x], st.get(i + 1, H.size()));
	for (int v: G[u]) {
		int i = ma[v];
		st.set(i, st.get(i, i + 1) - 1);
		dfs_ans(v, G, h, ma, H, st, ans);
		st.set(i, st.get(i, i + 1) + 1);
	}
	for (int v: G[u]) {
		int i = ma[v];
		st.set(i, st.get(i, i + 1) - 1);
	}
}

int main() {
	int N; cin >> N;
	vector<int> l(N);
	rep(u, N) scanf("%d", &l[u]);
	vector<vector<int> > G(N);
	for (int u = 1; u < N; u++) {
		int v; scanf("%d", &v); v--;
		G[v].pb(u);
	}
	vector<int> h(N), ma(N);
	dfs_h(0, G, l, h, ma);
	vector<int> H = h;
	sort(H.begin(), H.end());
	H.erase(unique(H.begin(), H.end()), H.end());
	int M = H.size();
	rep(u, N) {
		h[u] = lower_bound(H.begin(), H.end(), h[u]) - H.begin();
		ma[u] = lower_bound(H.begin(), H.end(), ma[u]) - H.begin();
	}
	segtree<monoid> st(M);
	map<int, int> ans;
	for (int x: H) ans[x] = INF;
	dfs_ans(0, G, h, ma, H, st, ans);
	int Q; cin >> Q;
	while (Q--) {
		int x; scanf("%d", &x);
		if (ans.count(x) && ans[x] < INF) printf("%d\n", ans[x]);
		else printf("-1\n");
	}
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:108:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  rep(u, N) scanf("%d", &l[u]);
                              ^
./Main.cpp:111:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int v; scanf("%d", &v); v--;
                         ^
./Main.cpp:130:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d", &x);
                         ^

Judge Result