oj.uz

Submission #840636

# Submission time Handle Problem Language Result Execution time Memory
840636 2023-08-31T14:46:04 Z mat_jur Regions (IOI09_regions) C++17
21 / 100
 8000 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

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(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
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Incorrect 1 ms 208 KB Output isn't correct
3 Incorrect 5 ms 384 KB Output isn't correct
4 Incorrect 10 ms 336 KB Output isn't correct
5 Incorrect 13 ms 336 KB Output isn't correct
6 Correct 76 ms 684 KB Output is correct
7 Incorrect 156 ms 716 KB Output isn't correct
8 Incorrect 220 ms 860 KB Output isn't correct
9 Incorrect 322 ms 4620 KB Output isn't correct
10 Incorrect 348 ms 2788 KB Output isn't correct
11 Correct 93 ms 2948 KB Output is correct
12 Correct 166 ms 12088 KB Output is correct
13 Correct 131 ms 3580 KB Output is correct
14 Correct 148 ms 3576 KB Output is correct
15 Correct 224 ms 47676 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 20764 KB Output is correct
2 Correct 754 ms 9656 KB Output is correct
3 Correct 1349 ms 48936 KB Output is correct
4 Incorrect 1316 ms 8920 KB Output isn't correct
5 Incorrect 5477 ms 21312 KB Output isn't correct
6 Incorrect 1226 ms 11388 KB Output isn't correct
7 Incorrect 7925 ms 30256 KB Output isn't correct
8 Execution timed out 8025 ms 102428 KB Time limit exceeded
9 Runtime error 249 ms 131072 KB Execution killed with signal 9
10 Runtime error 84 ms 131072 KB Execution killed with signal 9
11 Runtime error 116 ms 131072 KB Execution killed with signal 9
12 Incorrect 1742 ms 102076 KB Output isn't correct
13 Runtime error 137 ms 131072 KB Execution killed with signal 9
14 Incorrect 4465 ms 118320 KB Output isn't correct
15 Runtime error 115 ms 131072 KB Execution killed with signal 9
16 Runtime error 99 ms 131072 KB Execution killed with signal 9
17 Runtime error 106 ms 131072 KB Execution killed with signal 9