Submission #840411

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
840411	2023-08-31T10:59:41 Z	mat_jur	Regions (IOI09_regions)	C++17	50 / 100	8000 ms	34248 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

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;
//	if (r <= 500) {brut1(n, r, q); return 0;}
	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);
	}

	vector<int> start(n), end(n);
	int timer = 0;
	function<void(int, int)> dfs = [&](int v, int p) {
		start[v] = timer++;
		for(auto w : G[v]) {
			if (w == p) continue;
			dfs(w, v);
		}
		end[v] = timer-1;
	};
	dfs(0, -1);
	REP(j, q) {
		int r1, r2;
		cin >> r1 >> r2;
		r1--; r2--;
		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 ans = 0;
		for (auto v : wyst[r1]) {
			ans += a[end[v]] - get(start[v]-1);	
		}
		cout << ans << '\n';
		cout.flush();
	}

	return 0;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	6 ms	336 KB	Output is correct
6	Correct	15 ms	464 KB	Output is correct
7	Correct	21 ms	336 KB	Output is correct
8	Correct	28 ms	464 KB	Output is correct
9	Correct	46 ms	1224 KB	Output is correct
10	Correct	93 ms	1120 KB	Output is correct
11	Correct	157 ms	1520 KB	Output is correct
12	Correct	219 ms	2276 KB	Output is correct
13	Correct	302 ms	2204 KB	Output is correct
14	Correct	376 ms	2676 KB	Output is correct
15	Correct	562 ms	7168 KB	Output is correct

Subtask #2

35.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4880 ms	7400 KB	Output is correct
2	Correct	6422 ms	6676 KB	Output is correct
3	Execution timed out	8054 ms	10360 KB	Time limit exceeded
4	Correct	631 ms	2952 KB	Output is correct
5	Correct	1018 ms	5692 KB	Output is correct
6	Correct	2191 ms	5036 KB	Output is correct
7	Correct	4388 ms	6504 KB	Output is correct
8	Correct	6164 ms	14728 KB	Output is correct
9	Execution timed out	8044 ms	14248 KB	Time limit exceeded
10	Execution timed out	8045 ms	22696 KB	Time limit exceeded
11	Execution timed out	8064 ms	17096 KB	Time limit exceeded
12	Execution timed out	8098 ms	15540 KB	Time limit exceeded
13	Execution timed out	8026 ms	17168 KB	Time limit exceeded
14	Execution timed out	8054 ms	16932 KB	Time limit exceeded
15	Execution timed out	8026 ms	23088 KB	Time limit exceeded
16	Execution timed out	8069 ms	34248 KB	Time limit exceeded
17	Execution timed out	8063 ms	31748 KB	Time limit exceeded