oj.uz

답안 #1013422

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1013422 2024-07-03T14:11:12 Z vjudge1 Regions (IOI09_regions) C++17
100 / 100
 3053 ms 39956 KB 
#include<bits/stdc++.h>
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 2e5 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int C = 500;
int frq[MAXN], col[MAXN];
int n, r, q;
vector<int> deco;
ll ans[503][25001];
pii upper;
vector<int> adj[MAXN];
int dt[MAXN], ft[MAXN], gtime = 1;
vector<int> dis_times[MAXN];
vector<int> nodes[MAXN];
void pre(int node){
	dis_times[col[node]].pb(gtime);
	nodes[col[node]].pb(node);
	dt[node] = gtime++;
	for (auto to : adj[node])
		pre(to);
	ft[node] = gtime - 1;
}
void dfs(int node, int cnt){
	ans[upper.S][col[node]] += cnt;
	if (col[node] == upper.F) cnt++;
	for (auto to : adj[node]){
		dfs(to, cnt);
	}
}
ll brut(int e1, int e2){
	ll res = 0;
	for (auto node : nodes[e1]){
		res += upper_bound(all(dis_times[e2]), ft[node]) - lower_bound(all(dis_times[e2]), dt[node]);
	}
	return res;
}

int main(){
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	cin >> n >> r >> q >> col[1];
	for (int i = 2; i <= n; i++){
		int p, c;
		cin >> p >> c;
		adj[p].pb(i);
		col[i] = c;
		frq[c]++;
	}
	pre(1);
	for (int i = 0; i <= 25000; i++){
		if (frq[i] >= C){
			deco.pb(i);
		}
	}
	//for (int i = 1; i <= r; i++){
		//upper = {i, i};
		//dfs(1, 0);
	//}
	for (int i = 0; i < sz(deco); i++){
		upper = {deco[i], i};
		dfs(1, 0);
	}
	while (q--){
		int e1, e2;
		cin >> e1 >> e2;
		if (frq[e1] >= C){
			cout << ans[lower_bound(all(deco), e1) - deco.begin()][e2] << endl;
		}
		else {
			cout << brut(e1, e2) << endl;
		}
	}
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 3 ms 19032 KB Output is correct
3 Correct 3 ms 19032 KB Output is correct
4 Correct 5 ms 19032 KB Output is correct
5 Correct 7 ms 19032 KB Output is correct
6 Correct 15 ms 19068 KB Output is correct
7 Correct 16 ms 19032 KB Output is correct
8 Correct 14 ms 19032 KB Output is correct
9 Correct 25 ms 19796 KB Output is correct
10 Correct 46 ms 19288 KB Output is correct
11 Correct 68 ms 19540 KB Output is correct
12 Correct 98 ms 20052 KB Output is correct
13 Correct 114 ms 19800 KB Output is correct
14 Correct 170 ms 20312 KB Output is correct
15 Correct 193 ms 22656 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1370 ms 24904 KB Output is correct
2 Correct 1469 ms 23632 KB Output is correct
3 Correct 1964 ms 26540 KB Output is correct
4 Correct 175 ms 20312 KB Output is correct
5 Correct 256 ms 21848 KB Output is correct
6 Correct 832 ms 25360 KB Output is correct
7 Correct 1179 ms 22096 KB Output is correct
8 Correct 953 ms 26704 KB Output is correct
9 Correct 1519 ms 26704 KB Output is correct
10 Correct 3053 ms 31316 KB Output is correct
11 Correct 2471 ms 25936 KB Output is correct
12 Correct 909 ms 27472 KB Output is correct
13 Correct 1272 ms 27560 KB Output is correct
14 Correct 1532 ms 31504 KB Output is correct
15 Correct 2146 ms 31812 KB Output is correct
16 Correct 2140 ms 36944 KB Output is correct
17 Correct 2067 ms 39956 KB Output is correct