Submission #840412

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
840412	2023-08-31T11:02:32 Z	mat_jur	Regions (IOI09_regions)	C++17	55 / 100	8000 ms	46628 KB

regions

#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define debug(X) ;
#endif
#define ll long long
#define all(v) (v).begin(), (v).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define ROF(i,r,l) for(int i=(r);i>=(l);--i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
#define fi first
#define se second
#define eb emplace_back

void brut1(int n, int r, int q) {
	vector<int> h(n);
	cin >> h[0];
	h[0]--;
	vector G(n, vector(0, 0));
	FOR(i, 1, n-1) {
		int p;
		cin >> p >> h[i];
		p--;
		h[i]--;
		G[p].eb(i);
		G[i].eb(p);
	}
	auto merge = [&](vector<int> &a, vector<int> &b) {
		REP(i, r) a[i] += b[i];
		return;
	};
	vector ans(r, vector(r, 0ll));
	function<vector<int>(int, int)> dfs = [&](int v, int p) {
		vector<int> cnt(r);
		for(auto w : G[v]) {
			if (w == p) continue;
			vector<int> b = dfs(w, v);
			merge(cnt, b);
		}
		REP(i, r) ans[h[v]][i] += cnt[i];
		cnt[h[v]]++;
		return cnt;
	};
	dfs(0, -1);
	REP(i, q) {
		int r1, r2;
		cin >> r1 >> r2;
		r1--; r2--;
		cout << ans[r1][r2] << '\n';
		cout.flush();
	}
};

int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, r, q;
	cin >> n >> r >> q;
	if (r <= 500) {brut1(n, r, q); return 0;}
	vector<int> h(n);
	vector G(n, vector(0, 0)), wyst(r, vector(0, 0));
	cin >> h[0];
	h[0]--;
	wyst[h[0]].eb(0);
	FOR(i, 1, n-1) {
		int p;
		cin >> p >> h[i];
		p--;
		h[i]--;
		wyst[h[i]].eb(i);
		G[p].eb(i);
		G[i].eb(p);
	}

	vector<int> start(n), end(n);
	int timer = 0;
	function<void(int, int)> dfs = [&](int v, int p) {
		start[v] = timer++;
		for(auto w : G[v]) {
			if (w == p) continue;
			dfs(w, v);
		}
		end[v] = timer-1;
	};
	dfs(0, -1);
	REP(j, q) {
		int r1, r2;
		cin >> r1 >> r2;
		r1--; r2--;
		vector<int> a(n, 0);
		for (auto v : wyst[r2]) {
			a[start[v]]++;
		}
		auto get = [&](int idx) {
			if (idx < 0) return 0;
			return a[idx];
		};
		REP(i, n) a[i] += get(i-1);
		ll ans = 0;
		for (auto v : wyst[r1]) {
			ans += a[end[v]] - get(start[v]-1);	
		}
		cout << ans << '\n';
		cout.flush();
	}

	return 0;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	1 ms	208 KB	Output is correct
4	Correct	3 ms	208 KB	Output is correct
5	Correct	5 ms	336 KB	Output is correct
6	Correct	12 ms	1744 KB	Output is correct
7	Correct	19 ms	592 KB	Output is correct
8	Correct	20 ms	976 KB	Output is correct
9	Correct	41 ms	7888 KB	Output is correct
10	Correct	53 ms	2640 KB	Output is correct
11	Correct	43 ms	2468 KB	Output is correct
12	Correct	73 ms	11476 KB	Output is correct
13	Correct	75 ms	2760 KB	Output is correct
14	Correct	94 ms	2768 KB	Output is correct
15	Correct	131 ms	46336 KB	Output is correct

Subtask #2

40.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	551 ms	18712 KB	Output is correct
2	Correct	581 ms	7464 KB	Output is correct
3	Correct	863 ms	46628 KB	Output is correct
4	Correct	600 ms	2944 KB	Output is correct
5	Correct	921 ms	5672 KB	Output is correct
6	Correct	2383 ms	5036 KB	Output is correct
7	Correct	4387 ms	6500 KB	Output is correct
8	Correct	6011 ms	14732 KB	Output is correct
9	Execution timed out	8028 ms	14216 KB	Time limit exceeded
10	Execution timed out	8025 ms	22680 KB	Time limit exceeded
11	Execution timed out	8054 ms	17080 KB	Time limit exceeded
12	Execution timed out	8021 ms	15524 KB	Time limit exceeded
13	Execution timed out	8036 ms	17084 KB	Time limit exceeded
14	Execution timed out	8016 ms	16936 KB	Time limit exceeded
15	Execution timed out	8026 ms	23056 KB	Time limit exceeded
16	Execution timed out	8022 ms	34320 KB	Time limit exceeded
17	Execution timed out	8069 ms	31772 KB	Time limit exceeded