oj.uz

답안 #840412

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
840412 2023-08-31T11:02:32 Z mat_jur Regions (IOI09_regions) C++17
55 / 100
 8000 ms 46628 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;
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 3 ms 208 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 12 ms 1744 KB Output is correct
7 Correct 19 ms 592 KB Output is correct
8 Correct 20 ms 976 KB Output is correct
9 Correct 41 ms 7888 KB Output is correct
10 Correct 53 ms 2640 KB Output is correct
11 Correct 43 ms 2468 KB Output is correct
12 Correct 73 ms 11476 KB Output is correct
13 Correct 75 ms 2760 KB Output is correct
14 Correct 94 ms 2768 KB Output is correct
15 Correct 131 ms 46336 KB Output is correct

Subtask #2
40.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 551 ms 18712 KB Output is correct
2 Correct 581 ms 7464 KB Output is correct
3 Correct 863 ms 46628 KB Output is correct
4 Correct 600 ms 2944 KB Output is correct
5 Correct 921 ms 5672 KB Output is correct
6 Correct 2383 ms 5036 KB Output is correct
7 Correct 4387 ms 6500 KB Output is correct
8 Correct 6011 ms 14732 KB Output is correct
9 Execution timed out 8028 ms 14216 KB Time limit exceeded
10 Execution timed out 8025 ms 22680 KB Time limit exceeded
11 Execution timed out 8054 ms 17080 KB Time limit exceeded
12 Execution timed out 8021 ms 15524 KB Time limit exceeded
13 Execution timed out 8036 ms 17084 KB Time limit exceeded
14 Execution timed out 8016 ms 16936 KB Time limit exceeded
15 Execution timed out 8026 ms 23056 KB Time limit exceeded
16 Execution timed out 8022 ms 34320 KB Time limit exceeded
17 Execution timed out 8069 ms 31772 KB Time limit exceeded