oj.uz

Submission #404279

# Submission time Handle Problem Language Result Execution time Memory
404279 2021-05-14T04:55:47 Z pure_mem Regions (IOI09_regions) C++14
55 / 100
 8000 ms 116656 KB 
#include <bits/stdc++.h> 
 
#define X first
#define Y second
#define MP make_pair
#define ll long long
 
using namespace std;
 
const int N = 2e5 + 12, BS = 300, M = 1340;
const ll INF = 1e18;

int n, m, q, timer, rv[N], cl[N];
ll ans1[M][25001], ans2[M][25001];
vector< int > g[N];
vector< pair<int, int> > his[N];

void dfs(int v){
	his[cl[v]].push_back(MP(++timer, 1));
	for(int to: g[v]){
		dfs(to);
	}
	his[cl[v]].push_back(MP(++timer, -1));		
}

ll calc(int x, int y){
	int i = 0, j = 0, tmp = 0;
	ll r = 0;
	while(i < his[x].size() && j < his[y].size()){
		if(i < his[x].size() && (j == his[y].size() || his[x][i].X < his[y][j].X))
			tmp += his[x][i++].Y;
		else{
			r += (his[y][j++].Y == 1 ? tmp: 0);
		}	
	}
	return r;
}

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m >> q >> cl[1];
	for(int i = 2, x;i <= n;i++){
		cin >> x >> cl[i];	
		g[x].push_back(i);
	}
	dfs(1);
	for(int i = 1, z = 0;i <= m;i++){
		if(his[i].size() >= BS){
			rv[i] = ++z;
			for(int j = 1;j <= m;j++){
				ans1[z][j] = calc(i, j);
				if(his[j].size() < BS)
					ans2[z][j] = calc(j, i);
			}		
		}
	}
	for(int i = 1, x, y;i <= q;i++){
		cin >> x >> y;
		if(rv[x])
			cout << ans1[rv[x]][y] << endl;
		else if(rv[y])
			cout << ans2[rv[y]][x] << endl;
		else
			cout << calc(x, y) << endl;		
	}
}

Compilation message

regions.cpp: In function 'long long int calc(int, int)':
regions.cpp:29:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  while(i < his[x].size() && j < his[y].size()){
      |        ~~^~~~~~~~~~~~~~~
regions.cpp:29:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  while(i < his[x].size() && j < his[y].size()){
      |                             ~~^~~~~~~~~~~~~~~
regions.cpp:30:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   if(i < his[x].size() && (j == his[y].size() || his[x][i].X < his[y][j].X))
      |      ~~^~~~~~~~~~~~~~~
regions.cpp:30:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   if(i < his[x].size() && (j == his[y].size() || his[x][i].X < his[y][j].X))
      |                            ~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9672 KB Output is correct
2 Correct 6 ms 9672 KB Output is correct
3 Correct 10 ms 9672 KB Output is correct
4 Correct 10 ms 9672 KB Output is correct
5 Correct 17 ms 9672 KB Output is correct
6 Correct 26 ms 9800 KB Output is correct
7 Correct 47 ms 9800 KB Output is correct
8 Correct 39 ms 9800 KB Output is correct
9 Correct 54 ms 10296 KB Output is correct
10 Correct 121 ms 10276 KB Output is correct
11 Correct 98 ms 10624 KB Output is correct
12 Correct 173 ms 11208 KB Output is correct
13 Correct 198 ms 10912 KB Output is correct
14 Correct 307 ms 12804 KB Output is correct
15 Correct 480 ms 17372 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1024 ms 15976 KB Output is correct
2 Correct 1016 ms 15464 KB Output is correct
3 Correct 1879 ms 18532 KB Output is correct
4 Correct 452 ms 15168 KB Output is correct
5 Correct 418 ms 13556 KB Output is correct
6 Correct 1815 ms 19828 KB Output is correct
7 Correct 2824 ms 26624 KB Output is correct
8 Correct 3850 ms 36080 KB Output is correct
9 Execution timed out 8084 ms 107024 KB Time limit exceeded
10 Execution timed out 8087 ms 116428 KB Time limit exceeded
11 Execution timed out 8021 ms 106024 KB Time limit exceeded
12 Execution timed out 8102 ms 98136 KB Time limit exceeded
13 Execution timed out 8016 ms 92536 KB Time limit exceeded
14 Execution timed out 8036 ms 80672 KB Time limit exceeded
15 Execution timed out 8039 ms 114108 KB Time limit exceeded
16 Execution timed out 8085 ms 116656 KB Time limit exceeded
17 Execution timed out 8013 ms 105816 KB Time limit exceeded