oj.uz

Submission #404284

# Submission time Handle Problem Language Result Execution time Memory
404284 2021-05-14T05:05:12 Z pure_mem Regions (IOI09_regions) C++14
25 / 100
 6193 ms 32992 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 = 500, M = N * 2 / BS + 2;
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
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 10 ms 9672 KB Output is correct
5 Correct 12 ms 9708 KB Output is correct
6 Correct 27 ms 9800 KB Output is correct
7 Correct 48 ms 9800 KB Output is correct
8 Correct 36 ms 9800 KB Output is correct
9 Correct 95 ms 10312 KB Output is correct
10 Correct 76 ms 10184 KB Output is correct
11 Correct 153 ms 10568 KB Output is correct
12 Correct 134 ms 11208 KB Output is correct
13 Correct 204 ms 10824 KB Output is correct
14 Correct 240 ms 11568 KB Output is correct
15 Correct 316 ms 14648 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 914 ms 14856 KB Output isn't correct
2 Incorrect 1174 ms 13880 KB Output isn't correct
3 Incorrect 2190 ms 16888 KB Output isn't correct
4 Correct 242 ms 11464 KB Output is correct
5 Correct 452 ms 13460 KB Output is correct
6 Incorrect 915 ms 12844 KB Output isn't correct
7 Incorrect 1046 ms 14048 KB Output isn't correct
8 Incorrect 1164 ms 20216 KB Output isn't correct
9 Incorrect 2352 ms 20332 KB Output isn't correct
10 Incorrect 1933 ms 25696 KB Output isn't correct
11 Incorrect 6193 ms 21220 KB Output isn't correct
12 Incorrect 1028 ms 20856 KB Output isn't correct
13 Incorrect 1598 ms 21304 KB Output isn't correct
14 Incorrect 1874 ms 20868 KB Output isn't correct
15 Incorrect 2460 ms 25884 KB Output isn't correct
16 Incorrect 2520 ms 32992 KB Output isn't correct
17 Incorrect 2761 ms 32052 KB Output isn't correct