Submission #840606

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
840606	2023-08-31T14:23:48 Z	mat_jur	Regions (IOI09_regions)	C++17	21 / 100	1491 ms	131072 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

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

	int n, r, q;
	cin >> n >> r >> q;
	vector<int> h(n);
	vector G(n, vector(0, 0)), wyst(r, vector(0, 0));
	cin >> h[0];
	h[0]--;
	FOR(i, 1, n-1) {
		int p;
		cin >> p >> h[i];
		p--;
		h[i]--;
		G[p].eb(i);
		G[i].eb(p);
	}
	const int B = (int(sqrt(r))); 
	vector<int> big, bigIdx(n, -1);
	vector<int> start(n), end(n), s(n);
	int timer = 0;
	function<void(int, int)> dfs2 = [&](int v, int p) {
		start[v] = timer++;
		s[v] = 1;
		for(auto w : G[v]) {
			if (w == p) continue;
			dfs2(w, v);
			s[v] += s[w];
		}
		end[v] = timer-1;
	};
	dfs2(0, -1);
	REP(i, n) wyst[h[i]].eb(start[i]);

	REP(i, r) {
		if (ssize(wyst[i]) > B) {big.eb(i); bigIdx[i] = ssize(big)-1;}
	}
	auto merge = [&](vector<int> &a, vector<int> &b) {
		REP(i, ssize(big)) a[i] += b[i];
		return;
	};
	vector ans(r, vector(ssize(big), 0ll));
	function<vector<int>(int, int)> dfs = [&](int v, int p) {
		vector<int> cnt(ssize(big));
		for(auto w : G[v]) {
			if (w == p) continue;
			vector<int> b = dfs(w, v);
			merge(cnt, b);
		}
		REP(i, ssize(big)) ans[h[v]][i] += cnt[i];
		if(bigIdx[h[v]] >= 0) cnt[bigIdx[h[v]]]++;
		return cnt;
	};
	dfs(0, -1);

	REP(j, q) {
		int r1, r2;
		cin >> r1 >> r2;
		r1--; r2--;
		if (bigIdx[r2] >= 0) {
//			cerr << "CASE 1 \n";
			cout << ans[r1][bigIdx[r2]] << '\n';
			cout.flush();
			continue;
		}
		ll res = 0;
		for (auto v : wyst[r2]) {
			auto up = upper_bound(all(wyst[r1]), end[v])-1, low = lower_bound(all(wyst[r1]), start[v]);
			res += up-low+1;
		}
		cout << res << '\n';
		cout.flush();
	}

	return 0;
}

Subtask #1

6.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	208 KB	Output isn't correct
2	Correct	1 ms	208 KB	Output is correct
3	Incorrect	2 ms	208 KB	Output isn't correct
4	Incorrect	3 ms	208 KB	Output isn't correct
5	Incorrect	6 ms	336 KB	Output isn't correct
6	Incorrect	11 ms	464 KB	Output isn't correct
7	Incorrect	11 ms	464 KB	Output isn't correct
8	Incorrect	23 ms	464 KB	Output isn't correct
9	Incorrect	43 ms	4176 KB	Output isn't correct
10	Incorrect	55 ms	2384 KB	Output isn't correct
11	Correct	100 ms	2852 KB	Output is correct
12	Correct	138 ms	11952 KB	Output is correct
13	Correct	117 ms	3320 KB	Output is correct
14	Correct	106 ms	3280 KB	Output is correct
15	Correct	143 ms	47284 KB	Output is correct

Subtask #2

15.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	512 ms	20308 KB	Output is correct
2	Correct	538 ms	9104 KB	Output is correct
3	Correct	889 ms	48416 KB	Output is correct
4	Incorrect	138 ms	7120 KB	Output isn't correct
5	Incorrect	166 ms	20932 KB	Output isn't correct
6	Incorrect	352 ms	10308 KB	Output isn't correct
7	Incorrect	466 ms	16888 KB	Output isn't correct
8	Incorrect	748 ms	101756 KB	Output isn't correct
9	Incorrect	1356 ms	130324 KB	Output isn't correct
10	Runtime error	98 ms	131072 KB	Execution killed with signal 9
11	Runtime error	98 ms	131072 KB	Execution killed with signal 9
12	Incorrect	767 ms	100460 KB	Output isn't correct
13	Runtime error	137 ms	131072 KB	Execution killed with signal 9
14	Incorrect	1491 ms	116412 KB	Output isn't correct
15	Runtime error	99 ms	131072 KB	Execution killed with signal 9
16	Runtime error	90 ms	131072 KB	Execution killed with signal 9
17	Runtime error	98 ms	131072 KB	Execution killed with signal 9