oj.uz

답안 #1033311

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1033311 2024-07-24T16:22:53 Z s_tree Regions (IOI09_regions) C++17
100 / 100
 4048 ms 48132 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define vt vector
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

template<class T> bool chmin(T& a, const T& b) {
	return b<a?a=b, 1:0;
}
template<class T> bool chmax(T& a, const T& b) { 
	return a<b?a=b, 1:0;
} 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng_64(chrono::steady_clock::now().time_since_epoch().count());


const int B = 300;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	int n, r, q;
	cin >> n >> r >> q;
	vt<vt<int>> g(n+1);
	vt<vt<int>> col(r+1);
	vt<int> c(n+1);
	vt<vt<ll>> precomp(r+1);
	for(int i = 1;i<=n;i++) {
		if(i>1) {
			int par;
			cin >> par;
			g[par].pb(i);
		}
		int h;
		cin >> h;
		c[i] = h;
		col[h].pb(i);
	}
	vt<int> tin(n+1), tout(n+1);
	int timer=0;
	vt<vt<int>> tinCol(n+1);
	vt<vt<int>> toutCol(n+1);
	auto dfs = [&](int at,  auto &&dfs) -> void {
		tin[at]=++timer;	
		tinCol[c[at]].pb(tin[at]);
		for(int to:g[at]) {
			dfs(to, dfs);
		}
		tout[at]=++timer;
		toutCol[c[at]].pb(tout[at]);
	};
	int fixedCol=0;
	auto dfs2 = [&](int at,  auto &&dfs2) -> int {
		int cnt=0;
		for(int to:g[at]) {
			cnt+=dfs2(to, dfs2);
		}
		precomp[fixedCol][c[at]]+=cnt;
		cnt+=(fixedCol==c[at]);
		return cnt;
	};
	dfs(1, dfs);
	for(int i = 1;i<=r;i++) {
		if(sz(col[i])>B) {
			fixedCol=i;
			precomp[i].resize(r+1);
			dfs2(1, dfs2);
		}
	}
	while(q--) {
		int r1, r2;
		cin >> r1 >> r2;
		if(sz(col[r2])>B) {
			cout << precomp[r2][r1] << endl;
		}
		else {
			ll ans=0;
			for(int i:col[r2]) {
				ans+=lower_bound(all(tinCol[r1]), tin[i])-tinCol[r1].begin();
				ans-=lower_bound(all(toutCol[r1]), tin[i])-toutCol[r1].begin();
			}
			cout << ans << endl;
		}
	}

}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 9 ms 600 KB Output is correct
7 Correct 10 ms 600 KB Output is correct
8 Correct 19 ms 600 KB Output is correct
9 Correct 25 ms 1112 KB Output is correct
10 Correct 42 ms 1872 KB Output is correct
11 Correct 64 ms 2392 KB Output is correct
12 Correct 92 ms 3408 KB Output is correct
13 Correct 121 ms 3364 KB Output is correct
14 Correct 184 ms 4412 KB Output is correct
15 Correct 147 ms 7268 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1355 ms 10636 KB Output is correct
2 Correct 1980 ms 10072 KB Output is correct
3 Correct 2273 ms 13332 KB Output is correct
4 Correct 178 ms 4704 KB Output is correct
5 Correct 223 ms 6560 KB Output is correct
6 Correct 429 ms 10976 KB Output is correct
7 Correct 963 ms 14228 KB Output is correct
8 Correct 928 ms 24732 KB Output is correct
9 Correct 1980 ms 27888 KB Output is correct
10 Correct 2334 ms 48132 KB Output is correct
11 Correct 4048 ms 45524 KB Output is correct
12 Correct 1109 ms 26728 KB Output is correct
13 Correct 1543 ms 26724 KB Output is correct
14 Correct 1787 ms 31104 KB Output is correct
15 Correct 2336 ms 32084 KB Output is correct
16 Correct 1977 ms 35836 KB Output is correct
17 Correct 2210 ms 37944 KB Output is correct