oj.uz

답안 #840629

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
840629 2023-08-31T14:43:43 Z mat_jur Regions (IOI09_regions) C++17
23 / 100
 8000 ms 74932 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 = 4*(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
13.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 5 ms 336 KB Output is correct
4 Correct 21 ms 352 KB Output is correct
5 Correct 56 ms 336 KB Output is correct
6 Correct 65 ms 548 KB Output is correct
7 Correct 207 ms 736 KB Output is correct
8 Correct 260 ms 1004 KB Output is correct
9 Correct 528 ms 2180 KB Output is correct
10 Correct 1198 ms 3264 KB Output is correct
11 Incorrect 3129 ms 7172 KB Output isn't correct
12 Correct 3539 ms 8744 KB Output is correct
13 Incorrect 3475 ms 9228 KB Output isn't correct
14 Correct 134 ms 3596 KB Output is correct
15 Correct 183 ms 47804 KB Output is correct

Subtask #2
10.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 655 ms 20792 KB Output is correct
2 Incorrect 834 ms 9144 KB Output isn't correct
3 Correct 1131 ms 48936 KB Output is correct
4 Execution timed out 8067 ms 17320 KB Time limit exceeded
5 Execution timed out 8060 ms 21388 KB Time limit exceeded
6 Incorrect 1057 ms 11328 KB Output isn't correct
7 Execution timed out 8026 ms 26836 KB Time limit exceeded
8 Execution timed out 8042 ms 54108 KB Time limit exceeded
9 Execution timed out 8093 ms 33024 KB Time limit exceeded
10 Execution timed out 8071 ms 45340 KB Time limit exceeded
11 Execution timed out 8018 ms 36600 KB Time limit exceeded
12 Execution timed out 8039 ms 34512 KB Time limit exceeded
13 Execution timed out 8021 ms 38664 KB Time limit exceeded
14 Execution timed out 8090 ms 41236 KB Time limit exceeded
15 Execution timed out 8007 ms 48792 KB Time limit exceeded
16 Execution timed out 8015 ms 66280 KB Time limit exceeded
17 Execution timed out 8039 ms 74932 KB Time limit exceeded