oj.uz

답안 #440792

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
440792 2021-07-03T05:11:27 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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5576 KB Output is correct
2 Correct 6 ms 5576 KB Output is correct
3 Correct 5 ms 5576 KB Output is correct
4 Correct 10 ms 5736 KB Output is correct
5 Correct 18 ms 5844 KB Output is correct
6 Correct 34 ms 6108 KB Output is correct
7 Correct 39 ms 6476 KB Output is correct
8 Correct 63 ms 6768 KB Output is correct
9 Correct 99 ms 8784 KB Output is correct
10 Correct 333 ms 11716 KB Output is correct
11 Correct 809 ms 14948 KB Output is correct
12 Correct 762 ms 18504 KB Output is correct
13 Correct 1346 ms 20984 KB Output is correct
14 Correct 2655 ms 24848 KB Output is correct
15 Correct 3149 ms 34216 KB Output is correct

Subtask #2
20.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8025 ms 56428 KB Time limit exceeded
2 Execution timed out 8074 ms 59300 KB Time limit exceeded
3 Execution timed out 8048 ms 68288 KB Time limit exceeded
4 Correct 2572 ms 25776 KB Output is correct
5 Correct 2496 ms 32472 KB Output is correct
6 Correct 3050 ms 41496 KB Output is correct
7 Correct 2752 ms 52900 KB Output is correct
8 Execution timed out 8029 ms 78700 KB Time limit exceeded
9 Execution timed out 8080 ms 111716 KB Time limit exceeded
10 Execution timed out 8077 ms 130572 KB Time limit exceeded
11 Runtime error 592 ms 131076 KB Execution killed with signal 9
12 Runtime error 499 ms 131076 KB Execution killed with signal 9
13 Runtime error 459 ms 131076 KB Execution killed with signal 9
14 Runtime error 532 ms 131076 KB Execution killed with signal 9
15 Runtime error 474 ms 131076 KB Execution killed with signal 9
16 Runtime error 687 ms 131076 KB Execution killed with signal 9
17 Runtime error 461 ms 131076 KB Execution killed with signal 9