oj.uz

답안 #840691

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
840691 2023-08-31T15:53:49 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;
			assert(ssize(wyst2[r2]) <= B);
			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;
			assert(ssize(wyst2[r1]) <= B);
			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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 208 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 22 ms 336 KB Output is correct
5 Correct 55 ms 440 KB Output is correct
6 Correct 60 ms 512 KB Output is correct
7 Correct 211 ms 692 KB Output is correct
8 Correct 261 ms 792 KB Output is correct
9 Correct 560 ms 2300 KB Output is correct
10 Correct 1285 ms 3260 KB Output is correct
11 Correct 3396 ms 7956 KB Output is correct
12 Correct 3379 ms 8800 KB Output is correct
13 Correct 6027 ms 13856 KB Output is correct
14 Execution timed out 8087 ms 20128 KB Time limit exceeded
15 Execution timed out 8087 ms 28064 KB Time limit exceeded

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8057 ms 33372 KB Time limit exceeded
2 Execution timed out 8048 ms 29452 KB Time limit exceeded
3 Execution timed out 8021 ms 34180 KB Time limit exceeded
4 Execution timed out 8090 ms 16480 KB Time limit exceeded
5 Execution timed out 8082 ms 20500 KB Time limit exceeded
6 Incorrect 1086 ms 23372 KB Output isn't correct
7 Execution timed out 8034 ms 38876 KB Time limit exceeded
8 Execution timed out 8087 ms 79444 KB Time limit exceeded
9 Execution timed out 8055 ms 33004 KB Time limit exceeded
10 Execution timed out 8100 ms 131072 KB Time limit exceeded
11 Execution timed out 8061 ms 38376 KB Time limit exceeded
12 Execution timed out 8055 ms 37948 KB Time limit exceeded
13 Execution timed out 8023 ms 40568 KB Time limit exceeded
14 Execution timed out 8064 ms 58484 KB Time limit exceeded
15 Execution timed out 8099 ms 50144 KB Time limit exceeded
16 Execution timed out 8035 ms 65628 KB Time limit exceeded
17 Execution timed out 8099 ms 81240 KB Time limit exceeded