oj.uz

Submission #404276

# Submission time Handle Problem Language Result Execution time Memory
404276 2021-05-14T04:51:28 Z pure_mem Regions (IOI09_regions) C++14
70 / 100
 8000 ms 112692 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[N / BS + 1][N], ans2[N / BS + 1][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){
			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 6 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 11 ms 9672 KB Output is correct
5 Correct 15 ms 9800 KB Output is correct
6 Correct 22 ms 9800 KB Output is correct
7 Correct 32 ms 9712 KB Output is correct
8 Correct 48 ms 9800 KB Output is correct
9 Correct 59 ms 10312 KB Output is correct
10 Correct 46 ms 10184 KB Output is correct
11 Correct 140 ms 10636 KB Output is correct
12 Correct 122 ms 11208 KB Output is correct
13 Correct 196 ms 10824 KB Output is correct
14 Correct 243 ms 11572 KB Output is correct
15 Correct 287 ms 14764 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1277 ms 16548 KB Output is correct
2 Correct 1153 ms 16372 KB Output is correct
3 Correct 2167 ms 21688 KB Output is correct
4 Correct 336 ms 11512 KB Output is correct
5 Correct 333 ms 13468 KB Output is correct
6 Correct 1828 ms 20148 KB Output is correct
7 Correct 2428 ms 24044 KB Output is correct
8 Correct 3856 ms 36676 KB Output is correct
9 Correct 4957 ms 44872 KB Output is correct
10 Execution timed out 8042 ms 106508 KB Time limit exceeded
11 Execution timed out 8029 ms 108592 KB Time limit exceeded
12 Execution timed out 8108 ms 72848 KB Time limit exceeded
13 Execution timed out 8047 ms 68328 KB Time limit exceeded
14 Execution timed out 8021 ms 30092 KB Time limit exceeded
15 Correct 6782 ms 26456 KB Output is correct
16 Execution timed out 8044 ms 112692 KB Time limit exceeded
17 Correct 7592 ms 42548 KB Output is correct