oj.uz

Submission #404273

# Submission time Handle Problem Language Result Execution time Memory
404273 2021-05-14T04:48:03 Z pure_mem Regions (IOI09_regions) C++14
95 / 100
 8000 ms 65604 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 () {
	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 6 ms 9672 KB Output is correct
2 Correct 6 ms 9672 KB Output is correct
3 Correct 7 ms 9672 KB Output is correct
4 Correct 12 ms 9672 KB Output is correct
5 Correct 13 ms 9672 KB Output is correct
6 Correct 31 ms 9672 KB Output is correct
7 Correct 41 ms 9800 KB Output is correct
8 Correct 50 ms 9800 KB Output is correct
9 Correct 58 ms 10340 KB Output is correct
10 Correct 105 ms 10184 KB Output is correct
11 Correct 87 ms 10500 KB Output is correct
12 Correct 122 ms 11096 KB Output is correct
13 Correct 189 ms 10816 KB Output is correct
14 Correct 214 ms 11464 KB Output is correct
15 Correct 349 ms 14592 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1253 ms 15084 KB Output is correct
2 Correct 1229 ms 13700 KB Output is correct
3 Correct 1819 ms 17032 KB Output is correct
4 Correct 334 ms 11456 KB Output is correct
5 Correct 318 ms 13424 KB Output is correct
6 Correct 1916 ms 20180 KB Output is correct
7 Correct 1840 ms 18324 KB Output is correct
8 Correct 3874 ms 36716 KB Output is correct
9 Correct 2052 ms 19944 KB Output is correct
10 Correct 7865 ms 65604 KB Output is correct
11 Correct 2471 ms 19184 KB Output is correct
12 Correct 4011 ms 21168 KB Output is correct
13 Correct 4689 ms 21568 KB Output is correct
14 Execution timed out 8039 ms 27712 KB Time limit exceeded
15 Correct 6651 ms 26452 KB Output is correct
16 Correct 6159 ms 33352 KB Output is correct
17 Correct 8000 ms 39192 KB Output is correct