oj.uz

Submission #53581

# Submission time Handle Problem Language Result Execution time Memory
53581 2018-06-30T09:03:01 Z ho94949 Regions (IOI09_regions) C++17
100 / 100
 6492 ms 67132 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31224 KB Output is correct
2 Correct 29 ms 31368 KB Output is correct
3 Correct 37 ms 31368 KB Output is correct
4 Correct 30 ms 31368 KB Output is correct
5 Correct 34 ms 31368 KB Output is correct
6 Correct 45 ms 31512 KB Output is correct
7 Correct 67 ms 31684 KB Output is correct
8 Correct 60 ms 31684 KB Output is correct
9 Correct 75 ms 32256 KB Output is correct
10 Correct 112 ms 32572 KB Output is correct
11 Correct 128 ms 33088 KB Output is correct
12 Correct 187 ms 33872 KB Output is correct
13 Correct 305 ms 33896 KB Output is correct
14 Correct 359 ms 34760 KB Output is correct
15 Correct 377 ms 37052 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1340 ms 39564 KB Output is correct
2 Correct 2000 ms 39564 KB Output is correct
3 Correct 2575 ms 43552 KB Output is correct
4 Correct 298 ms 43552 KB Output is correct
5 Correct 436 ms 43552 KB Output is correct
6 Correct 565 ms 43552 KB Output is correct
7 Correct 768 ms 43552 KB Output is correct
8 Correct 1281 ms 46524 KB Output is correct
9 Correct 2732 ms 54424 KB Output is correct
10 Correct 5199 ms 60104 KB Output is correct
11 Correct 6492 ms 60104 KB Output is correct
12 Correct 2375 ms 60104 KB Output is correct
13 Correct 2984 ms 60104 KB Output is correct
14 Correct 3161 ms 60104 KB Output is correct
15 Correct 4742 ms 63592 KB Output is correct
16 Correct 4788 ms 67132 KB Output is correct
17 Correct 4454 ms 67132 KB Output is correct