Submission #124773

#	Time	Username	Problem	Language	Result	Execution time	Memory
124773		arthurconmy	Regions (IOI09_regions)	C++14	12 / 100	8098 ms	18112 KiB

regions

// check ctrl+v :^)
/* Arthur Conmy IOI template - minimal! */
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>
using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = pair<int,int>;
#define pb push_back
#define ff first
#define ss second
#define REP(i,a,b) \
for(int i = int(a); i<=int(b); i++)

const int MAXN=int(2e5)+1;

int reg[MAXN];
bool vis[MAXN];
vi adj[MAXN];
ll ans=0;
ll cur_r1=0;
int r1,r2;

void dfs(int v)
{
	if(reg[v]==r1) cur_r1++;
	if(reg[v]==r2) ans+=cur_r1;

	for(auto u:adj[v])
	{
		if(vis[u]) continue;
		vis[u]=1;
		dfs(u);
	}

	if(reg[v]==r1) cur_r1--;
}

int main()
{
	#ifdef ARTHUR_LOCAL
		ifstream cin("input.txt");
	#endif

	int n,r,q;
	cin>>n>>r>>q;

	int h1;
	cin>>h1;

	reg[1]=h1;

	REP(i,2,n)
	{
		int s,h;
		cin>>s>>h;

		adj[s].pb(i);
		adj[i].pb(s);
		reg[i]=h;
	}

	REP(QUERY,1,q)
	{
		// int r1,r2;
		cin>>r1>>r2;

		vis[1]=1;
		dfs(1);

		cout << ans << endl;

		REP(i,0,MAXN-1) vis[i]=0;
		ans=0;
		cur_r1=0;
	}
}

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