oj.uz

Submission #404274

# Submission time Handle Problem Language Result Execution time Memory
404274 2021-05-14T04:49:36 Z pure_mem Regions (IOI09_regions) C++14
90 / 100
 8000 ms 65616 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 = 400;
const ll INF = 1e18;

int n, m, q, timer, rv[N], cl[N];
ll ans1[BS][N], ans2[BS][N];
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 + BS){
			rv[i] = ++z;
			for(int j = 1;j <= m;j++)
				ans1[z][j] = calc(i, j), 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 7 ms 9672 KB Output is correct
2 Correct 7 ms 9672 KB Output is correct
3 Correct 8 ms 9672 KB Output is correct
4 Correct 13 ms 9672 KB Output is correct
5 Correct 16 ms 9672 KB Output is correct
6 Correct 28 ms 9800 KB Output is correct
7 Correct 28 ms 9752 KB Output is correct
8 Correct 45 ms 9764 KB Output is correct
9 Correct 59 ms 10312 KB Output is correct
10 Correct 109 ms 10184 KB Output is correct
11 Correct 106 ms 10648 KB Output is correct
12 Correct 184 ms 11208 KB Output is correct
13 Correct 224 ms 10920 KB Output is correct
14 Correct 244 ms 11584 KB Output is correct
15 Correct 232 ms 14732 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1179 ms 15116 KB Output is correct
2 Correct 1096 ms 13720 KB Output is correct
3 Correct 1703 ms 17052 KB Output is correct
4 Correct 239 ms 11512 KB Output is correct
5 Correct 362 ms 13460 KB Output is correct
6 Correct 1879 ms 20188 KB Output is correct
7 Correct 1969 ms 18436 KB Output is correct
8 Correct 4176 ms 36760 KB Output is correct
9 Correct 1880 ms 19952 KB Output is correct
10 Execution timed out 8038 ms 65616 KB Time limit exceeded
11 Correct 2979 ms 19212 KB Output is correct
12 Correct 4579 ms 21032 KB Output is correct
13 Correct 4946 ms 21480 KB Output is correct
14 Execution timed out 8035 ms 26960 KB Time limit exceeded
15 Correct 6818 ms 26384 KB Output is correct
16 Correct 6286 ms 33328 KB Output is correct
17 Correct 7218 ms 39320 KB Output is correct