Submission #1002841

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1002841	2024-06-19T20:28:43 Z	Tob	Regions (IOI09_regions)	C++14	100 / 100	2391 ms	33872 KB

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;
}

Compilation message

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.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6232 KB	Output is correct
2	Correct	2 ms	6232 KB	Output is correct
3	Correct	3 ms	6232 KB	Output is correct
4	Correct	5 ms	6232 KB	Output is correct
5	Correct	7 ms	6232 KB	Output is correct
6	Correct	13 ms	6232 KB	Output is correct
7	Correct	17 ms	6188 KB	Output is correct
8	Correct	21 ms	6232 KB	Output is correct
9	Correct	32 ms	6744 KB	Output is correct
10	Correct	57 ms	6744 KB	Output is correct
11	Correct	81 ms	7000 KB	Output is correct
12	Correct	111 ms	7512 KB	Output is correct
13	Correct	118 ms	7768 KB	Output is correct
14	Correct	173 ms	8096 KB	Output is correct
15	Correct	198 ms	10584 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	771 ms	11896 KB	Output is correct
2	Correct	818 ms	11088 KB	Output is correct
3	Correct	1365 ms	14344 KB	Output is correct
4	Correct	207 ms	8532 KB	Output is correct
5	Correct	262 ms	9560 KB	Output is correct
6	Correct	693 ms	9808 KB	Output is correct
7	Correct	911 ms	10884 KB	Output is correct
8	Correct	795 ms	15440 KB	Output is correct
9	Correct	1292 ms	16720 KB	Output is correct
10	Correct	1868 ms	21328 KB	Output is correct
11	Correct	2391 ms	19280 KB	Output is correct
12	Correct	883 ms	18000 KB	Output is correct
13	Correct	1177 ms	19280 KB	Output is correct
14	Correct	1536 ms	21660 KB	Output is correct
15	Correct	1697 ms	24760 KB	Output is correct
16	Correct	1753 ms	33780 KB	Output is correct
17	Correct	1721 ms	33872 KB	Output is correct