Submission #933053

#	Time	Username	Problem	Language	Result	Execution time	Memory
933053		vjudge1	Regions (IOI09_regions)	C++17	13 / 100	306 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;
	vector<int> mp;
	nodo()
	{
		mp.resize(501);
		lson = nullptr; rson = nullptr;
	}
};
void une (vector<int>&a, vector<int>&b)
{
	for (int i = 0; i <= 500; i++)
		a[i]+=b[i];
}
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;
		une(x->mp, x->rson->mp);
	}
	vector<int> query (ptr(nodo) node, const int &l, const int &r)
	{
		int currL = node->l, currR = node->r; vector<int>mp(501);
		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); vector<int> mp2 = query(node->rson, l, r);

		une(mp, mp2);
		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++)
	{
		vector<int> temp = segtree.query(segtree.raiz, ini[i], fin[i]-1);
		int yo = region[i];
		for (int i = 0; i <= 500; i++)
		{
			resp[yo][i]+=temp[i];
		}
	}

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

Compilation message (stderr)

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

• Subtask 1: 13 / 15
• Subtask 2: 0 / 85