oj.uz

Submission #840439

# Submission time Handle Problem Language Result Execution time Memory
840439 2023-08-31T11:31:04 Z mat_jur Regions (IOI09_regions) C++17
50 / 100
 1833 ms 131072 KB 
#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;
	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);
	}
	const int B = int(sqrt(r));
	vector<int> big, bigIdx(n, -1);
	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);

	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);
	vector pref(ssize(big), vector(n, 0));
	REP(i, ssize(big)) {
		for (auto w : wyst[big[i]]) {
			pref[i][start[w]]++;
			if(end[w]+1 < n) pref[i][end[w]+1]--;
		}
		auto get = [&](int idx) {
			if (idx < 0) return 0;
			return pref[i][idx];
		};
		REP(j, n) pref[i][j] += get(j-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;
		}
		if (bigIdx[r1] == -1 && bigIdx[r2] == -1) {
//			cerr << "CASE 2 \n";
			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 res = 0;
			for (auto v : wyst[r1]) {
				res += a[end[v]] - get(start[v]-1);	
			}
			cout << res << '\n';
			cout.flush();
			continue;
		}
		if (bigIdx[r1] >= 0 && bigIdx[r2] == -1) {
//			cerr << "CASE 3 \n";
			ll res = 0;
			for (auto v : wyst[r2]) {
				res += pref[bigIdx[r1]][start[v]];	
			}
			cout << res << '\n';
			cout.flush();
			continue;
		}
	}

	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 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 5 ms 336 KB Output is correct
5 Correct 4 ms 464 KB Output is correct
6 Correct 14 ms 464 KB Output is correct
7 Correct 21 ms 592 KB Output is correct
8 Correct 36 ms 840 KB Output is correct
9 Correct 50 ms 4048 KB Output is correct
10 Correct 77 ms 14480 KB Output is correct
11 Correct 73 ms 18108 KB Output is correct
12 Correct 139 ms 39428 KB Output is correct
13 Correct 138 ms 35144 KB Output is correct
14 Correct 131 ms 26788 KB Output is correct
15 Correct 146 ms 46924 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 68432 KB Output is correct
2 Correct 562 ms 77708 KB Output is correct
3 Correct 1018 ms 104468 KB Output is correct
4 Correct 330 ms 18364 KB Output is correct
5 Correct 1045 ms 25876 KB Output is correct
6 Correct 1833 ms 21588 KB Output is correct
7 Correct 1596 ms 42508 KB Output is correct
8 Runtime error 142 ms 131072 KB Execution killed with signal 9
9 Runtime error 389 ms 131072 KB Execution killed with signal 9
10 Runtime error 74 ms 131072 KB Execution killed with signal 9
11 Runtime error 79 ms 131072 KB Execution killed with signal 9
12 Runtime error 443 ms 131072 KB Execution killed with signal 9
13 Runtime error 143 ms 131072 KB Execution killed with signal 9
14 Runtime error 373 ms 131072 KB Execution killed with signal 9
15 Runtime error 84 ms 131072 KB Execution killed with signal 9
16 Runtime error 96 ms 131072 KB Execution killed with signal 9
17 Runtime error 92 ms 131072 KB Execution killed with signal 9