Submission #840629

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
840629	2023-08-31T14:43:43 Z	mat_jur	Regions (IOI09_regions)	C++17	23 / 100	8000 ms	74932 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)), wyst2(r, vector(0, 0));
	cin >> h[0];
	h[0]--;
	wyst2[h[0]].eb(0);
	FOR(i, 1, n-1) {
		int p;
		cin >> p >> h[i];
		p--;
		h[i]--;
		wyst2[h[i]].eb(i);
		G[p].eb(i);
		G[i].eb(p);
	}
	const int B = 4*(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;
		wyst[h[v]].eb(start[v]);
		for(auto w : G[v]) {
			if (w == p) continue;
			dfs2(w, v);
			s[v] += s[w];
		}
		end[v] = timer-1;
	};
	dfs2(0, -1);
	debug(start);
	debug(end);
	debug(wyst);

	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[r1] >= 0) {
			cerr << "CASE 1 \n";
			cout << ans[r1][bigIdx[r2]] << '\n';
			cout.flush();
			continue;
		}
		cerr << "CASE 2 \n";
		ll res = 0;
		for (auto v : wyst2[r1]) {
			auto up = upper_bound(all(wyst[r2]), end[v])-1, low = lower_bound(all(wyst[r2]), start[v]);
			cerr << v << ' ' << up-wyst[r2].begin() << ' ' << low-wyst[r2].begin() << '\n';
			res += up-low+1;
		}
		cout << res << '\n';
		cout.flush();
	}

	return 0;
}

Subtask #1

13.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	5 ms	336 KB	Output is correct
4	Correct	21 ms	352 KB	Output is correct
5	Correct	56 ms	336 KB	Output is correct
6	Correct	65 ms	548 KB	Output is correct
7	Correct	207 ms	736 KB	Output is correct
8	Correct	260 ms	1004 KB	Output is correct
9	Correct	528 ms	2180 KB	Output is correct
10	Correct	1198 ms	3264 KB	Output is correct
11	Incorrect	3129 ms	7172 KB	Output isn't correct
12	Correct	3539 ms	8744 KB	Output is correct
13	Incorrect	3475 ms	9228 KB	Output isn't correct
14	Correct	134 ms	3596 KB	Output is correct
15	Correct	183 ms	47804 KB	Output is correct

Subtask #2

10.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	655 ms	20792 KB	Output is correct
2	Incorrect	834 ms	9144 KB	Output isn't correct
3	Correct	1131 ms	48936 KB	Output is correct
4	Execution timed out	8067 ms	17320 KB	Time limit exceeded
5	Execution timed out	8060 ms	21388 KB	Time limit exceeded
6	Incorrect	1057 ms	11328 KB	Output isn't correct
7	Execution timed out	8026 ms	26836 KB	Time limit exceeded
8	Execution timed out	8042 ms	54108 KB	Time limit exceeded
9	Execution timed out	8093 ms	33024 KB	Time limit exceeded
10	Execution timed out	8071 ms	45340 KB	Time limit exceeded
11	Execution timed out	8018 ms	36600 KB	Time limit exceeded
12	Execution timed out	8039 ms	34512 KB	Time limit exceeded
13	Execution timed out	8021 ms	38664 KB	Time limit exceeded
14	Execution timed out	8090 ms	41236 KB	Time limit exceeded
15	Execution timed out	8007 ms	48792 KB	Time limit exceeded
16	Execution timed out	8015 ms	66280 KB	Time limit exceeded
17	Execution timed out	8039 ms	74932 KB	Time limit exceeded