oj.uz

Submission #440793

# Submission time Handle Problem Language Result Execution time Memory
440793 2021-07-03T05:17:47 Z zeyu Regions (IOI09_regions) C++17
35 / 100
 8000 ms 131076 KB 
#include <bits/stdc++.h>
#define maxn 200020
#define maxm 25025
using namespace std;
vector<int> graph[maxn];
int tin[maxn], tout[maxn];
vector<int> region[maxm];
map<pair<int, int>, int> mp;
int n, q, r, x, y, timer = 0;

struct vertex{
	int sum; vertex *l, *r;
	
	vertex(int val){
		sum = val; l = 0; r = 0;
	}
	
	vertex(vertex *_l, vertex *_r){
		l = _l; r = _r;
		sum = _l -> sum + _r -> sum;
	}
};

struct segtree{
	int sz;
	
	vertex* build(int lx, int rx){
		if (rx - lx == 1){
			return new vertex(0);
		}
		int mid = (lx + rx) >> 1;
		return new vertex(build(lx, mid), build(mid, rx));
	}
	
	vertex* build(int n){
		sz = n;
		return build(0, sz);
	}
	
	vertex* set(int i, vertex* v, int lx, int rx){
		if (rx - lx == 1){
			return new vertex(1);
		}
		int mid = (lx + rx) >> 1;
		if (i < mid) return new vertex(set(i, v -> l, lx, mid), v -> r);
		else return new vertex(v -> l, set(i, v -> r, mid, rx));
	}
	
	vertex* set(int i, vertex* v){
		return set(i, v, 0, sz);
	}
	
	int calc(int l, int r, vertex* v, int lx, int rx){
		if (lx >= r || rx <= l) return 0;
		if (lx >= l && rx <= r) return v -> sum;
		int mid = (lx + rx) >> 1;
		return calc(l, r, v -> l, lx, mid) + calc(l, r, v -> r, mid, rx);
	}
	
	int calc(int l, int r, vertex* v){
		return calc(l, r, v, 0, sz);
	}
};

void dfs(int x, int p){
	tin[x] = timer ++;
	for (int i = 0; i < graph[x].size(); i ++){
		int to = graph[x][i];
		if (to != p) dfs(to, x);
	}
	tout[x] = timer;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> r >> q;
	cin >> x; x --;
	region[x].push_back(0);
	for (int i = 1; i < n; i ++){
		cin >> y >> x;
		x --; y --;
		region[x].push_back(i);
		graph[i].push_back(y);
		graph[y].push_back(i);
	}
	dfs(0, 0);
	segtree st;
	vector<vertex*> hist;
	hist.push_back(st.build(n));
	vector<int> sz(r + 1);
	for (int i = 1; i <= r; i ++) sz[i] = sz[i - 1] + region[i - 1].size();
	for (int i = 0; i < r; i ++){
		for (int j = 0; j < region[i].size(); j ++){
			hist.push_back(st.set(tin[region[i][j]], hist.back()));
		}
	}
	while(q --){
		int r1, r2;
		cin >> r1 >> r2;
		r1 --; r2 --;
		int ans = 0;
		if (mp.count(make_pair(r1, r2))){
			ans = mp[make_pair(r1, r2)];
		} else{
			for (int i = 0; i < region[r1].size(); i ++){
				int cur = region[r1][i];
				ans += st.calc(tin[cur], tout[cur], hist[sz[r2 + 1]]) - st.calc(tin[cur], tout[cur], hist[sz[r2]]);			
			}
			mp[make_pair(r1, r2)] = ans;
		}
		cout << ans << endl;
	}
}

Compilation message

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for (int i = 0; i < graph[x].size(); i ++){
      |                  ~~^~~~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:94:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for (int j = 0; j < region[i].size(); j ++){
      |                   ~~^~~~~~~~~~~~~~~~~~
regions.cpp:106:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |    for (int i = 0; i < region[r1].size(); i ++){
      |                    ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5576 KB Output is correct
2 Correct 5 ms 5576 KB Output is correct
3 Correct 6 ms 5576 KB Output is correct
4 Correct 8 ms 5680 KB Output is correct
5 Correct 11 ms 5848 KB Output is correct
6 Correct 23 ms 6232 KB Output is correct
7 Correct 50 ms 6492 KB Output is correct
8 Correct 57 ms 6800 KB Output is correct
9 Correct 101 ms 8884 KB Output is correct
10 Correct 315 ms 11672 KB Output is correct
11 Correct 679 ms 14968 KB Output is correct
12 Correct 758 ms 18548 KB Output is correct
13 Correct 1466 ms 20992 KB Output is correct
14 Correct 2558 ms 24840 KB Output is correct
15 Correct 3066 ms 34232 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8048 ms 56420 KB Time limit exceeded
2 Execution timed out 8016 ms 59128 KB Time limit exceeded
3 Execution timed out 8069 ms 68236 KB Time limit exceeded
4 Correct 2493 ms 25668 KB Output is correct
5 Correct 2526 ms 32356 KB Output is correct
6 Correct 2754 ms 41372 KB Output is correct
7 Correct 2898 ms 52896 KB Output is correct
8 Execution timed out 8066 ms 78684 KB Time limit exceeded
9 Execution timed out 8025 ms 111764 KB Time limit exceeded
10 Execution timed out 8080 ms 130664 KB Time limit exceeded
11 Runtime error 550 ms 131076 KB Execution killed with signal 9
12 Runtime error 805 ms 131076 KB Execution killed with signal 9
13 Runtime error 482 ms 131076 KB Execution killed with signal 9
14 Runtime error 516 ms 131076 KB Execution killed with signal 9
15 Runtime error 488 ms 131076 KB Execution killed with signal 9
16 Runtime error 459 ms 131076 KB Execution killed with signal 9
17 Runtime error 519 ms 131076 KB Execution killed with signal 9