Submission #53581

#	Time	Username	Problem	Language	Result	Execution time	Memory
53581		ho94949	Regions (IOI09_regions)	C++17	100 / 100	6492 ms	67132 KiB

regions

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 262144;
int N, R, Q;
int p[MAXN], c[MAXN]; // parent, color
vector<int> people[MAXN]; // people base on color
vector<int> child[MAXN]; // child of orig vertex
 
int dfsorder[MAXN]; // dfs order of orig vertex
int endinter[MAXN]; // end itnerval of orig vertex
int dfsorderinv[MAXN]; // dfs order inverse array
 
int dfs(int a)
{
	static int tp = 0;
	++tp;
	
	dfsorder[a] = tp;
	dfsorderinv[tp] = a;
	
	for(auto x: child[a])
		dfs(x);
	endinter[a] = tp;
}
 
namespace Q1 //type 1 query: small parent, heavy child
{
	vector<int> pos[MAXN]; //position based on color
	void init()
	{
		for(int i=1; i<=N; ++i)
			pos[c[dfsorderinv[i]]].push_back(i);
	}
	int query(int r1, int r2)
	{
		//for each r1 interv, count
		int ans = 0;
		for(auto x: people[r1])
		{
			int s = dfsorder[x];
			int e = endinter[x];
			ans += upper_bound(pos[r2].begin(), pos[r2].end(), e)
				 - lower_bound(pos[r2].begin(), pos[r2].end(), s);
		}
		return ans;
	}
}
namespace Q2 //type 2 query: heavy parent, small child
{
	vector<int> pos[MAXN]; //position
	vector<int> acc[MAXN]; //accumulated
	void init()
	{
		for(int i=1; i<=R; ++i)
		{
			vector<pair<int, int> > V;
			for(auto x: people[i])
			{
				V.emplace_back(dfsorder[x], +1);
				V.emplace_back(endinter[x]+1, -1);
			}
			sort(V.begin(), V.end());
			pos[i].push_back(-1);
			acc[i].push_back(0);
			for(auto t: V)
			{
				pos[i].push_back(t.first);
				acc[i].push_back(acc[i][acc[i].size()-1] + t.second);
			}
		}
	}
	int query(int r1, int r2)
	{
		int ans = 0;
		for(auto x: people[r2])
		{
			int ind = lower_bound(pos[r1].begin(), pos[r1].end(), dfsorder[x]+1)
					- pos[r1].begin() - 1;
			ans += acc[r1][ind];
		}
		return ans;
	}
}
 
void init()
{
	dfs(1); //we've done dfs ordering
	Q1::init();
	Q2::init();
}
 
 
 
int query(int r1, int r2)
{
	if(people[r1].size() < people[r2].size()) return Q1::query(r1, r2);
	else return Q2::query(r1, r2);    
}
 
int main()
{
	scanf("%d%d%d", &N, &R, &Q);
	scanf("%d", c+1);
	people[c[1]].push_back(1);
	for(int i=2; i<=N; ++i)
	{
		scanf("%d%d", p+i, c+i);
		people[c[i]].push_back(i);
		child[p[i]].push_back(i);
	}
	init();
	map<pair<int, int>, int> M;
	for(int i=0; i<Q; ++i)
	{
		int a, b; scanf("%d%d", &a, &b);
		if(M.find(make_pair(a, b)) == M.end())
			M[make_pair(a, b)] = query(a, b);
		printf("%d\n", M[make_pair(a, b)]);
		fflush(stdout);
	}
	return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int dfs(int)':
regions.cpp:24:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
regions.cpp: In function 'int main()':
regions.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &R, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:103:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", c+1);
  ~~~~~^~~~~~~~~~~
regions.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", p+i, c+i);
   ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp:115:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~

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