oj.uz

답안 #840606

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
840606 2023-08-31T14:23:48 Z mat_jur Regions (IOI09_regions) C++17
21 / 100
 1491 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));
	cin >> h[0];
	h[0]--;
	FOR(i, 1, n-1) {
		int p;
		cin >> p >> h[i];
		p--;
		h[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;
		for(auto w : G[v]) {
			if (w == p) continue;
			dfs2(w, v);
			s[v] += s[w];
		}
		end[v] = timer-1;
	};
	dfs2(0, -1);
	REP(i, n) wyst[h[i]].eb(start[i]);

	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[r2] >= 0) {
//			cerr << "CASE 1 \n";
			cout << ans[r1][bigIdx[r2]] << '\n';
			cout.flush();
			continue;
		}
		ll res = 0;
		for (auto v : wyst[r2]) {
			auto up = upper_bound(all(wyst[r1]), end[v])-1, low = lower_bound(all(wyst[r1]), start[v]);
			res += up-low+1;
		}
		cout << res << '\n';
		cout.flush();
	}

	return 0;
}

Subtask #1
6.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 208 KB Output isn't correct
2 Correct 1 ms 208 KB Output is correct
3 Incorrect 2 ms 208 KB Output isn't correct
4 Incorrect 3 ms 208 KB Output isn't correct
5 Incorrect 6 ms 336 KB Output isn't correct
6 Incorrect 11 ms 464 KB Output isn't correct
7 Incorrect 11 ms 464 KB Output isn't correct
8 Incorrect 23 ms 464 KB Output isn't correct
9 Incorrect 43 ms 4176 KB Output isn't correct
10 Incorrect 55 ms 2384 KB Output isn't correct
11 Correct 100 ms 2852 KB Output is correct
12 Correct 138 ms 11952 KB Output is correct
13 Correct 117 ms 3320 KB Output is correct
14 Correct 106 ms 3280 KB Output is correct
15 Correct 143 ms 47284 KB Output is correct

Subtask #2
15.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 512 ms 20308 KB Output is correct
2 Correct 538 ms 9104 KB Output is correct
3 Correct 889 ms 48416 KB Output is correct
4 Incorrect 138 ms 7120 KB Output isn't correct
5 Incorrect 166 ms 20932 KB Output isn't correct
6 Incorrect 352 ms 10308 KB Output isn't correct
7 Incorrect 466 ms 16888 KB Output isn't correct
8 Incorrect 748 ms 101756 KB Output isn't correct
9 Incorrect 1356 ms 130324 KB Output isn't correct
10 Runtime error 98 ms 131072 KB Execution killed with signal 9
11 Runtime error 98 ms 131072 KB Execution killed with signal 9
12 Incorrect 767 ms 100460 KB Output isn't correct
13 Runtime error 137 ms 131072 KB Execution killed with signal 9
14 Incorrect 1491 ms 116412 KB Output isn't correct
15 Runtime error 99 ms 131072 KB Execution killed with signal 9
16 Runtime error 90 ms 131072 KB Execution killed with signal 9
17 Runtime error 98 ms 131072 KB Execution killed with signal 9