oj.uz

답안 #1033312

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1033312 2024-07-24T16:23:05 Z s_tree Regions (IOI09_regions) C++17
90 / 100
 2953 ms 131072 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 = 200;
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 1 ms 344 KB Output is correct
2 Correct 1 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 4 ms 344 KB Output is correct
6 Correct 9 ms 596 KB Output is correct
7 Correct 24 ms 600 KB Output is correct
8 Correct 25 ms 600 KB Output is correct
9 Correct 26 ms 1112 KB Output is correct
10 Correct 52 ms 1624 KB Output is correct
11 Correct 101 ms 2460 KB Output is correct
12 Correct 96 ms 3320 KB Output is correct
13 Correct 144 ms 3364 KB Output is correct
14 Correct 221 ms 4412 KB Output is correct
15 Correct 195 ms 7280 KB Output is correct

Subtask #2
75.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1144 ms 10760 KB Output is correct
2 Correct 902 ms 10336 KB Output is correct
3 Correct 2368 ms 13332 KB Output is correct
4 Correct 185 ms 4708 KB Output is correct
5 Correct 237 ms 6560 KB Output is correct
6 Correct 485 ms 10976 KB Output is correct
7 Correct 1047 ms 14296 KB Output is correct
8 Correct 830 ms 24736 KB Output is correct
9 Correct 1711 ms 34000 KB Output is correct
10 Correct 2183 ms 98020 KB Output is correct
11 Runtime error 2406 ms 131072 KB Execution killed with signal 9
12 Correct 2953 ms 62808 KB Output is correct
13 Correct 2461 ms 63556 KB Output is correct
14 Correct 1840 ms 31088 KB Output is correct
15 Correct 2343 ms 32088 KB Output is correct
16 Runtime error 1100 ms 131072 KB Execution killed with signal 9
17 Correct 2230 ms 37956 KB Output is correct