제출 #933052

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
933052		vjudge1	Regions (IOI09_regions)	C++17	25 / 100	8038 ms	131072 KiB

regions

#include <bits/stdc++.h>
#include <map>
using namespace std;
#define ptr(x) shared_ptr<x>
const int maxn = 2e5 + 54;

int region[maxn];
vector<int>adj[maxn];
int euler[maxn]; int ini[maxn], fin[maxn];
int resp[550][550];
int pos = 0;
int n, r, q; 
void dfs(int yo, int padre)
{
	ini[yo] = pos;
	euler[pos++] = yo;
	for (int v: adj[yo])
		if (v != padre) dfs(v, yo);
	fin[yo] = pos;
}
struct nodo
{
	ptr(nodo) lson, rson;
	int l, r;
	map<int, int> mp;
	nodo()
	{
		lson = nullptr; rson = nullptr;
	}
};
struct mst 
{
	ptr(nodo) raiz;
	mst()
	{
		raiz = (ptr(nodo))(new nodo);	
		build(raiz, 0, n-1);
	}
	void build (ptr(nodo) x, int l, int r)
	{
		x->l = l; x->r = r;
		if (l == r)
		{
			x->mp[region[euler[l]]]++;
			return;
		}
		x->lson = (ptr(nodo))(new nodo); x->rson = (ptr(nodo))(new nodo);	
		int mit = (l+r)>>1;
		build(x->lson, l, mit); build(x->rson, mit+1, r);
		x->mp = x->lson->mp;
		for (auto it: x->rson->mp)
			x->mp[it.first] += it.second;
	}
	map<int, int> query (ptr(nodo) node, const int &l, const int &r)
	{
		int currL = node->l, currR = node->r; map<int, int>mp;
		if (currR < l || r < currL) return mp;
		if (l <= currL && currR <= r) return node->mp;
		int mit = (l+r)>>1;
		mp = query(node->lson, l, r); map<int, int> mp2 = query(node->rson, l, r);

		for (auto it: mp2)
			mp[it.first] += it.second;
		return mp;
	}
};
int main() 
{
	cin >> n >> r >> q;
	cin >> region[0]; int padre;
	for (int i = 1; i < n; i++)
	{
		cin >> padre; padre--; cin >> region[i];
		adj[padre].push_back(i);
		adj[i].push_back(padre);
	}
	dfs(0, -1);
	mst segtree;
	//l;

// << ini[i] << " " << fin[i] << endl;
	for (int i = 0; i < n; i++)
	{
		map<int, int> temp = segtree.query(segtree.raiz, ini[i], fin[i]-1);
		int yo = region[i];
		for (auto it: temp)
		{
			resp[yo][it.first]+=it.second;
		}
	}

	
	int a, b;
	while (q--)
	{
		cin >> a >> b;
		cout << resp[a][b] << endl;
	}
}

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

regions.cpp: In member function 'std::map<int, int> mst::query(std::shared_ptr<nodo>, const int&, const int&)':
regions.cpp:59:7: warning: unused variable 'mit' [-Wunused-variable]
   59 |   int mit = (l+r)>>1;
      |       ^~~

• Subtask 1: 15 / 15
• Subtask 2: 10 / 85