제출 #1002841

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1002841		Tob	Regions (IOI09_regions)	C++14	100 / 100	2391 ms	33872 KiB

regions

#include <bits/stdc++.h>

#define ll long long
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef pair <ll, ll> pii;

const int N = 2e5 + 7, R = 25007, B = 900;

int n, r, q, tim, pl;
int a[N], st[N], en[N], po[N], cov[B][R], cr[B][R], enn[N];
vector <int> adj[N], wh[R], wh2[R];

void dfs(int x, int p = 0) {
	st[x] = ++tim;
	wh[a[x]].pb(x);
	wh2[a[x]].pb(x);
	for (auto it : adj[x]) {
		if (it == p) continue;
		dfs(it, x);
	}
	en[x] = tim;
}

void dfs2(int x, int cur, int y, int p = 0) {
	if (a[x] == y) pl++;
	cov[cur][a[x]] += pl;
	for (auto it : adj[x]) {
		if (it == p) continue;
		dfs2(it, cur, y, x);
	}
	if (a[x] == y) pl--;
}

int dfs3(int x, int cur, int y, int p = 0) {
	int cnt = (a[x] == y);
	for (auto it : adj[x]) {
		if (it == p) continue;
		cnt += dfs3(it, cur, y, x);
	}
	cr[cur][a[x]] += cnt;
	return cnt;
}

bool cmp(int x, int y) {
	return st[x] < st[y];
}
bool cmp2(int x, int y) {
	return en[x] < en[y];
}

int main () {
	cin >> n >> r >> q;
	
	for (int i = 1; i <= n; i++) {
		if (i > 1) {
			int p; cin >> p;
			adj[i].pb(p);
			adj[p].pb(i);
		}
		cin >> a[i];
	}
	
	dfs(1);
	
	int cnt = 0;
	for (int i = 1; i <= r; i++) {
		if (wh[i].size() >= B) {//-------------------------------
			po[i] = cnt;
			dfs2(1, cnt, i);
			dfs3(1, cnt, i);
			cnt++;
		}
	}
	
	for (int i = 1; i <= r; i++) {
		sort(all(wh[i]), cmp);
		sort(all(wh2[i]), cmp2);
	}
	
	while (q--) {
		int x, y; cin >> x >> y;
		if (wh[x].size() >= B) cout << cov[po[x]][y] << endl;//-----
		else if (wh[y].size() >= B) cout << cr[po[y]][x] << endl;//------
		else {
			vector <int> v;
			v.pb(-1e9);
			for (int i = 0; i < wh[y].size(); i++) {
				v.pb(st[wh[y][i]]);
			}
			v.pb(1e9);
			int res = 0, cu = 0;
			for (auto it : wh2[x]) {
				while (v[cu] <= en[it]) cu++;
				enn[it] = cu;
			}
			cu = 0;
			for (auto it : wh[x]) {
				while(v[cu] < st[it]) cu++;
				res += enn[it] - cu;
			}
			cout << res << endl;
		}
	}

	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

regions.cpp: In function 'int main()':
regions.cpp:94:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |    for (int i = 0; i < wh[y].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85