oj.uz

답안 #1033313

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1033313 2024-07-24T16:23:59 Z s_tree Regions (IOI09_regions) C++17
100 / 100
 3561 ms 36508 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 = 1000;
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 2 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 9 ms 600 KB Output is correct
7 Correct 14 ms 608 KB Output is correct
8 Correct 14 ms 852 KB Output is correct
9 Correct 24 ms 1112 KB Output is correct
10 Correct 72 ms 1788 KB Output is correct
11 Correct 82 ms 2460 KB Output is correct
12 Correct 90 ms 3324 KB Output is correct
13 Correct 129 ms 3360 KB Output is correct
14 Correct 200 ms 4412 KB Output is correct
15 Correct 189 ms 7268 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1599 ms 10624 KB Output is correct
2 Correct 2117 ms 10072 KB Output is correct
3 Correct 2262 ms 13336 KB Output is correct
4 Correct 199 ms 4696 KB Output is correct
5 Correct 241 ms 6556 KB Output is correct
6 Correct 1111 ms 7696 KB Output is correct
7 Correct 1358 ms 10384 KB Output is correct
8 Correct 919 ms 16896 KB Output is correct
9 Correct 1876 ms 22256 KB Output is correct
10 Correct 3410 ms 28496 KB Output is correct
11 Correct 3561 ms 26660 KB Output is correct
12 Correct 1012 ms 26736 KB Output is correct
13 Correct 1409 ms 26732 KB Output is correct
14 Correct 1782 ms 29652 KB Output is correct
15 Correct 2173 ms 32088 KB Output is correct
16 Correct 1770 ms 35832 KB Output is correct
17 Correct 2080 ms 36508 KB Output is correct