oj.uz

답안 #1033307

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1033307 2024-07-24T16:19:45 Z s_tree Regions (IOI09_regions) C++17
100 / 100
 3579 ms 37940 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 = 500;
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 1 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 12 ms 600 KB Output is correct
7 Correct 10 ms 600 KB Output is correct
8 Correct 17 ms 600 KB Output is correct
9 Correct 25 ms 1112 KB Output is correct
10 Correct 48 ms 1792 KB Output is correct
11 Correct 86 ms 2476 KB Output is correct
12 Correct 96 ms 3316 KB Output is correct
13 Correct 122 ms 3408 KB Output is correct
14 Correct 205 ms 4412 KB Output is correct
15 Correct 190 ms 7504 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1483 ms 10832 KB Output is correct
2 Correct 1939 ms 10088 KB Output is correct
3 Correct 2188 ms 13336 KB Output is correct
4 Correct 191 ms 4944 KB Output is correct
5 Correct 268 ms 6560 KB Output is correct
6 Correct 1146 ms 7696 KB Output is correct
7 Correct 1413 ms 10384 KB Output is correct
8 Correct 1014 ms 16896 KB Output is correct
9 Correct 1938 ms 22256 KB Output is correct
10 Correct 3373 ms 28496 KB Output is correct
11 Correct 3579 ms 26668 KB Output is correct
12 Correct 1105 ms 26736 KB Output is correct
13 Correct 1598 ms 26724 KB Output is correct
14 Correct 1868 ms 31096 KB Output is correct
15 Correct 2483 ms 32084 KB Output is correct
16 Correct 2069 ms 35832 KB Output is correct
17 Correct 2290 ms 37940 KB Output is correct