oj.uz

답안 #840697

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
840697 2023-08-31T15:59:17 Z mat_jur Regions (IOI09_regions) C++17
100 / 100
 3889 ms 45724 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);

	REP(i, r) {
		if (ssize(wyst[i]) > B) {big.eb(i); bigIdx[i] = ssize(big)-1;}
	}
	vector ans(ssize(big), vector(r, 0ll));
	REP(i, ssize(big)) {
		vector<int> pref(n);
		for (auto w : wyst2[big[i]]) {
			pref[start[w]]++;
			if(end[w]+1 < n) pref[end[w]+1]--;
		}
		auto get = [&](int idx) {
			if (idx < 0) return 0;
			return pref[idx];
		};
		REP(j, n) pref[j] += get(j-1);
		REP(j, r) {
			for (auto w : wyst2[j]) ans[i][j] += pref[start[w]];
		}
	};

	REP(j, q) {
		int r1, r2;
		cin >> r1 >> r2;
		r1--; r2--;
		if (bigIdx[r1] >= 0) {
			cout << ans[bigIdx[r1]][r2]<< '\n';
			cout.flush();
			continue;
		}
		if (bigIdx[r1] == -1) {
			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]);
				res += up-low+1;
			}
			cout << res << '\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 2 ms 208 KB Output is correct
4 Correct 3 ms 208 KB Output is correct
5 Correct 10 ms 336 KB Output is correct
6 Correct 18 ms 464 KB Output is correct
7 Correct 25 ms 464 KB Output is correct
8 Correct 12 ms 464 KB Output is correct
9 Correct 26 ms 1232 KB Output is correct
10 Correct 57 ms 1232 KB Output is correct
11 Correct 87 ms 1616 KB Output is correct
12 Correct 130 ms 2512 KB Output is correct
13 Correct 122 ms 2492 KB Output is correct
14 Correct 234 ms 3160 KB Output is correct
15 Correct 255 ms 7744 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1435 ms 8436 KB Output is correct
2 Correct 1788 ms 7812 KB Output is correct
3 Correct 2507 ms 11612 KB Output is correct
4 Correct 248 ms 3464 KB Output is correct
5 Correct 277 ms 6236 KB Output is correct
6 Correct 407 ms 9344 KB Output is correct
7 Correct 786 ms 11872 KB Output is correct
8 Correct 904 ms 24384 KB Output is correct
9 Correct 1790 ms 16576 KB Output is correct
10 Correct 2004 ms 45724 KB Output is correct
11 Correct 3889 ms 20304 KB Output is correct
12 Correct 1170 ms 19080 KB Output is correct
13 Correct 1676 ms 20576 KB Output is correct
14 Correct 1510 ms 24080 KB Output is correct
15 Correct 2563 ms 27320 KB Output is correct
16 Correct 2706 ms 38280 KB Output is correct
17 Correct 2322 ms 38980 KB Output is correct