oj.uz

답안 #1033305

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1033305 2024-07-24T16:18:14 Z s_tree Regions (IOI09_regions) C++17
80 / 100
 5324 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 = 100;
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 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 4 ms 344 KB Output is correct
6 Correct 8 ms 600 KB Output is correct
7 Correct 10 ms 600 KB Output is correct
8 Correct 15 ms 600 KB Output is correct
9 Correct 19 ms 1112 KB Output is correct
10 Correct 45 ms 1784 KB Output is correct
11 Correct 76 ms 2452 KB Output is correct
12 Correct 80 ms 3160 KB Output is correct
13 Correct 117 ms 3356 KB Output is correct
14 Correct 188 ms 4732 KB Output is correct
15 Correct 167 ms 7504 KB Output is correct

Subtask #2
65.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 701 ms 10916 KB Output is correct
2 Correct 796 ms 10332 KB Output is correct
3 Correct 965 ms 13824 KB Output is correct
4 Correct 209 ms 7832 KB Output is correct
5 Correct 260 ms 8360 KB Output is correct
6 Correct 451 ms 11088 KB Output is correct
7 Correct 780 ms 18064 KB Output is correct
8 Correct 888 ms 35852 KB Output is correct
9 Correct 2995 ms 92708 KB Output is correct
10 Runtime error 910 ms 131072 KB Execution killed with signal 9
11 Runtime error 2258 ms 131072 KB Execution killed with signal 9
12 Correct 5324 ms 101888 KB Output is correct
13 Correct 3701 ms 101880 KB Output is correct
14 Correct 4124 ms 111252 KB Output is correct
15 Runtime error 1504 ms 131072 KB Execution killed with signal 9
16 Runtime error 989 ms 131072 KB Execution killed with signal 9
17 Correct 2230 ms 118108 KB Output is correct