Submission #840697

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
840697	2023-08-31T15:59:17 Z	mat_jur	Regions (IOI09_regions)	C++17	100 / 100	3889 ms	45724 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 = (int(sqrt(n))); 
	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);

	REP(i, r) {
		if (ssize(wyst[i]) > B) {big.eb(i); bigIdx[i] = ssize(big)-1;}
	}
	vector ans(ssize(big), vector(r, 0ll));
	REP(i, ssize(big)) {
		vector<int> pref(n);
		for (auto w : wyst2[big[i]]) {
			pref[start[w]]++;
			if(end[w]+1 < n) pref[end[w]+1]--;
		}
		auto get = [&](int idx) {
			if (idx < 0) return 0;
			return pref[idx];
		};
		REP(j, n) pref[j] += get(j-1);
		REP(j, r) {
			for (auto w : wyst2[j]) ans[i][j] += pref[start[w]];
		}
	};

	REP(j, q) {
		int r1, r2;
		cin >> r1 >> r2;
		r1--; r2--;
		if (bigIdx[r1] >= 0) {
			cout << ans[bigIdx[r1]][r2]<< '\n';
			cout.flush();
			continue;
		}
		if (bigIdx[r1] == -1) {
			ll res = 0;
			assert(ssize(wyst2[r1]) <= B);
			for (auto v : wyst2[r1]) {
				auto up = upper_bound(all(wyst[r2]), end[v])-1, low = lower_bound(all(wyst[r2]), start[v]);
				res += up-low+1;
			}
			cout << res << '\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	2 ms	208 KB	Output is correct
4	Correct	3 ms	208 KB	Output is correct
5	Correct	10 ms	336 KB	Output is correct
6	Correct	18 ms	464 KB	Output is correct
7	Correct	25 ms	464 KB	Output is correct
8	Correct	12 ms	464 KB	Output is correct
9	Correct	26 ms	1232 KB	Output is correct
10	Correct	57 ms	1232 KB	Output is correct
11	Correct	87 ms	1616 KB	Output is correct
12	Correct	130 ms	2512 KB	Output is correct
13	Correct	122 ms	2492 KB	Output is correct
14	Correct	234 ms	3160 KB	Output is correct
15	Correct	255 ms	7744 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1435 ms	8436 KB	Output is correct
2	Correct	1788 ms	7812 KB	Output is correct
3	Correct	2507 ms	11612 KB	Output is correct
4	Correct	248 ms	3464 KB	Output is correct
5	Correct	277 ms	6236 KB	Output is correct
6	Correct	407 ms	9344 KB	Output is correct
7	Correct	786 ms	11872 KB	Output is correct
8	Correct	904 ms	24384 KB	Output is correct
9	Correct	1790 ms	16576 KB	Output is correct
10	Correct	2004 ms	45724 KB	Output is correct
11	Correct	3889 ms	20304 KB	Output is correct
12	Correct	1170 ms	19080 KB	Output is correct
13	Correct	1676 ms	20576 KB	Output is correct
14	Correct	1510 ms	24080 KB	Output is correct
15	Correct	2563 ms	27320 KB	Output is correct
16	Correct	2706 ms	38280 KB	Output is correct
17	Correct	2322 ms	38980 KB	Output is correct