oj.uz

Submission #404277

# Submission time Handle Problem Language Result Execution time Memory
404277 2021-05-14T04:54:10 Z pure_mem Regions (IOI09_regions) C++14
95 / 100
 8000 ms 64292 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 = 600, M = 600;
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 9 ms 9672 KB Output is correct
4 Correct 10 ms 9672 KB Output is correct
5 Correct 15 ms 9672 KB Output is correct
6 Correct 31 ms 9800 KB Output is correct
7 Correct 29 ms 9800 KB Output is correct
8 Correct 22 ms 9800 KB Output is correct
9 Correct 85 ms 10312 KB Output is correct
10 Correct 109 ms 10184 KB Output is correct
11 Correct 116 ms 10628 KB Output is correct
12 Correct 147 ms 11208 KB Output is correct
13 Correct 171 ms 10908 KB Output is correct
14 Correct 149 ms 11564 KB Output is correct
15 Correct 279 ms 14744 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1143 ms 15096 KB Output is correct
2 Correct 1156 ms 13652 KB Output is correct
3 Correct 2037 ms 17016 KB Output is correct
4 Correct 303 ms 11516 KB Output is correct
5 Correct 367 ms 13492 KB Output is correct
6 Correct 1857 ms 19780 KB Output is correct
7 Correct 2563 ms 22104 KB Output is correct
8 Correct 3950 ms 36084 KB Output is correct
9 Correct 3580 ms 32664 KB Output is correct
10 Correct 7973 ms 64292 KB Output is correct
11 Correct 7469 ms 57672 KB Output is correct
12 Correct 4604 ms 21472 KB Output is correct
13 Correct 4840 ms 21584 KB Output is correct
14 Execution timed out 8080 ms 27168 KB Time limit exceeded
15 Correct 6706 ms 26440 KB Output is correct
16 Correct 5829 ms 33372 KB Output is correct
17 Correct 7594 ms 39404 KB Output is correct