제출 #440793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
440793		zeyu	Regions (IOI09_regions)	C++17	35 / 100	8080 ms	131076 KiB

regions

#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;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 15
• Subtask 2: 20 / 85