oj.uz

Submission #404283

# Submission time Handle Problem Language Result Execution time Memory
404283 2021-05-14T05:04:07 Z pure_mem Regions (IOI09_regions) C++14
28 / 100
 8000 ms 37576 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));		
}
void dfs2(int v, int pa, int p1 = 0, int p2 = 0){
	p1 += cl[v] == pa, p2 += cl[v] != pa;
	ans1[rv[pa]][cl[v]] += p1;
	ans2[rv[pa]][cl[v]] += p2;
	for(int to: g[v]){
		dfs2(to, pa, p1, p2);
	}
	p1 -= cl[v] == pa, p2 -= cl[v] != pa;
}

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;
			dfs2(1, rv[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:38: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]
   38 |  while(i < his[x].size() && j < his[y].size()){
      |        ~~^~~~~~~~~~~~~~~
regions.cpp:38: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]
   38 |  while(i < his[x].size() && j < his[y].size()){
      |                             ~~^~~~~~~~~~~~~~~
regions.cpp:39: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]
   39 |   if(i < his[x].size() && (j == his[y].size() || his[x][i].X < his[y][j].X))
      |      ~~^~~~~~~~~~~~~~~
regions.cpp:39: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]
   39 |   if(i < his[x].size() && (j == his[y].size() || his[x][i].X < his[y][j].X))
      |                            ~~^~~~~~~~~~~~~~~~

Subtask #1
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9672 KB Output is correct
2 Correct 6 ms 9704 KB Output is correct
3 Correct 8 ms 9672 KB Output is correct
4 Correct 11 ms 9672 KB Output is correct
5 Correct 14 ms 9672 KB Output is correct
6 Correct 36 ms 9800 KB Output is correct
7 Correct 46 ms 9800 KB Output is correct
8 Correct 38 ms 9800 KB Output is correct
9 Correct 73 ms 10312 KB Output is correct
10 Correct 111 ms 10204 KB Output is correct
11 Correct 108 ms 10568 KB Output is correct
12 Correct 170 ms 11208 KB Output is correct
13 Correct 208 ms 10912 KB Output is correct
14 Incorrect 280 ms 12220 KB Output isn't correct
15 Incorrect 241 ms 17288 KB Output isn't correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1398 ms 17160 KB Output is correct
2 Incorrect 1387 ms 14920 KB Output isn't correct
3 Correct 1625 ms 20196 KB Output is correct
4 Incorrect 305 ms 11708 KB Output isn't correct
5 Correct 203 ms 13452 KB Output is correct
6 Incorrect 681 ms 12864 KB Output isn't correct
7 Incorrect 1259 ms 14020 KB Output isn't correct
8 Incorrect 977 ms 20112 KB Output isn't correct
9 Incorrect 4179 ms 22460 KB Output isn't correct
10 Incorrect 3200 ms 28528 KB Output isn't correct
11 Incorrect 7627 ms 22864 KB Output isn't correct
12 Execution timed out 8044 ms 25680 KB Time limit exceeded
13 Incorrect 7372 ms 27552 KB Output isn't correct
14 Execution timed out 8032 ms 26040 KB Time limit exceeded
15 Incorrect 4604 ms 32436 KB Output isn't correct
16 Incorrect 3634 ms 37576 KB Output isn't correct
17 Incorrect 3870 ms 37256 KB Output isn't correct