oj.uz

답안 #492343

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
492343 2021-12-06T21:35:10 Z keta_tsimakuridze Regions (IOI09_regions) C++14
80 / 100
 4295 ms 131076 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t, Bl = 200, n, r, q, c[N],idx = 0, tmin[N], tmout[N], id[N];
vector<int> heavy_p[25005], V[N];
vector<int> comp[N], x;
set<pii> occ[N];
void dfs(int u,int p) {
	tmin[u] = ++t;
	x[id[c[u]]]++;occ[c[u]].insert({tmin[u], occ[c[u]].size()});
	for(int i = 0; i < V[u].size(); i++) {
		dfs(V[u][i], u);
	}
	x[id[c[u]]]--;
	for(int i = 0; i < x.size(); i++) {
		heavy_p[c[u]][i] += x[i];
	}
	
	tmout[u] = t;
}
main(){
	cin >> n >> r >> q;
	cin >> c[1];
	for(int i = 2; i <= n; i++) {
		int p;
		cin >> p >> c[i];
		V[p].push_back(i);
	}
	for(int i = 1; i <= n; i++) {
		comp[c[i]].push_back(i);
	}
	idx = 0;
	for(int i = 1; i <= r; i++) {
		if(comp[i].size() >= Bl) {
			id[i] = ++idx;
		}
	}
	for(int i = 1; i <= r; i++) {
		heavy_p[i].resize(n/Bl + 2);
		occ[i].insert({0, 0});
	}
	x.resize(n/Bl + 2);
	dfs(1, 0);
	for(int i = 1; i <= r; i++) {
		occ[i].insert({n + 1, occ[i].size()});
	}
	while(q--) {
		int r1,r2;
		cin >> r1 >> r2;
		if(comp[r1].size() >= Bl) {
			cout << heavy_p[r2][id[r1]] << endl;
		}
		else {
			int ans = 0;
			for(int i = 0; i < comp[r1].size(); i++) {
				int l = tmin[comp[r1][i]], r = tmout[comp[r1][i]];
				ans += ((*occ[r2].upper_bound({r, n + 1})).s - 1 - (*--occ[r2].upper_bound({l - 1, n + 1})).s);
			}
			cout << ans << endl;
		}
	}
}

Compilation message

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:14:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
regions.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i = 0; i < x.size(); i++) {
      |                 ~~^~~~~~~~~~
regions.cpp: At global scope:
regions.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main(){
      | ^~~~
regions.cpp: In function 'int main()':
regions.cpp:37:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |   if(comp[i].size() >= Bl) {
      |      ~~~~~~~~~~~~~~~^~~~~
regions.cpp:53:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |   if(comp[r1].size() >= Bl) {
      |      ~~~~~~~~~~~~~~~~^~~~~
regions.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    for(int i = 0; i < comp[r1].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 19656 KB Output is correct
2 Correct 9 ms 19576 KB Output is correct
3 Correct 11 ms 19656 KB Output is correct
4 Correct 11 ms 19656 KB Output is correct
5 Correct 16 ms 19696 KB Output is correct
6 Correct 30 ms 19784 KB Output is correct
7 Correct 40 ms 19784 KB Output is correct
8 Correct 50 ms 19912 KB Output is correct
9 Correct 61 ms 20516 KB Output is correct
10 Correct 105 ms 20680 KB Output is correct
11 Correct 136 ms 21140 KB Output is correct
12 Correct 196 ms 22120 KB Output is correct
13 Correct 261 ms 21824 KB Output is correct
14 Correct 332 ms 22668 KB Output is correct
15 Correct 445 ms 26824 KB Output is correct

Subtask #2
65.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1738 ms 28076 KB Output is correct
2 Correct 1022 ms 26816 KB Output is correct
3 Correct 1374 ms 31336 KB Output is correct
4 Correct 395 ms 25296 KB Output is correct
5 Correct 415 ms 29492 KB Output is correct
6 Correct 666 ms 32668 KB Output is correct
7 Correct 1389 ms 41536 KB Output is correct
8 Correct 1440 ms 55332 KB Output is correct
9 Correct 3155 ms 81240 KB Output is correct
10 Correct 3568 ms 129640 KB Output is correct
11 Runtime error 669 ms 131076 KB Execution killed with signal 9
12 Correct 2644 ms 99572 KB Output is correct
13 Correct 3047 ms 100268 KB Output is correct
14 Correct 4295 ms 119092 KB Output is correct
15 Runtime error 183 ms 131076 KB Execution killed with signal 9
16 Runtime error 212 ms 131076 KB Execution killed with signal 9
17 Runtime error 1177 ms 131076 KB Execution killed with signal 9