oj.uz

Submission #840690

# Submission time Handle Problem Language Result Execution time Memory
840690 2023-08-31T15:48:54 Z mat_jur Regions (IOI09_regions) C++17
12 / 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(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);
	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);
	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] >= 0) {
			cerr << "CASE 3 \n";
			ll res = 0;
			for (auto v : wyst2[r2]) {
				res += pref[bigIdx[r1]][start[v]];	
			}
			cout << res << '\n';
			cout.flush();
			continue;
		}
		if (bigIdx[r1] == -1) {
			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
12.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 7 ms 328 KB Output is correct
4 Correct 17 ms 388 KB Output is correct
5 Correct 58 ms 532 KB Output is correct
6 Correct 59 ms 524 KB Output is correct
7 Correct 218 ms 756 KB Output is correct
8 Correct 321 ms 864 KB Output is correct
9 Correct 588 ms 2252 KB Output is correct
10 Correct 1316 ms 3220 KB Output is correct
11 Correct 3441 ms 8016 KB Output is correct
12 Correct 3224 ms 8824 KB Output is correct
13 Correct 5967 ms 13992 KB Output is correct
14 Execution timed out 8051 ms 20052 KB Time limit exceeded
15 Execution timed out 8007 ms 27808 KB Time limit exceeded

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8098 ms 33556 KB Time limit exceeded
2 Execution timed out 8096 ms 29508 KB Time limit exceeded
3 Execution timed out 8018 ms 34184 KB Time limit exceeded
4 Execution timed out 8090 ms 17072 KB Time limit exceeded
5 Execution timed out 8007 ms 21388 KB Time limit exceeded
6 Incorrect 1111 ms 23256 KB Output isn't correct
7 Execution timed out 8045 ms 39604 KB Time limit exceeded
8 Execution timed out 8082 ms 79752 KB Time limit exceeded
9 Execution timed out 8096 ms 33304 KB Time limit exceeded
10 Execution timed out 8044 ms 131072 KB Time limit exceeded
11 Execution timed out 8077 ms 39196 KB Time limit exceeded
12 Execution timed out 8086 ms 38196 KB Time limit exceeded
13 Execution timed out 8086 ms 40996 KB Time limit exceeded
14 Execution timed out 8053 ms 58892 KB Time limit exceeded
15 Execution timed out 8031 ms 50192 KB Time limit exceeded
16 Execution timed out 8013 ms 65696 KB Time limit exceeded
17 Execution timed out 8050 ms 81520 KB Time limit exceeded