oj.uz

Submission #211918

# Submission time Handle Problem Language Result Execution time Memory
211918 2020-03-21T17:41:24 Z Lawliet Regions (IOI09_regions) C++17
100 / 100
 5825 ms 44604 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;
typedef pair<int,int> pii;

const int MAXN = 200010;

int n, r, q;
int curTime;

int v[MAXN];

int tin[MAXN];
int tout[MAXN];
int prof[MAXN];

int indHeavy[MAXN];
int upAnswer[MAXN];

bool isHeavy[MAXN];

vector< int > adj[MAXN];
vector< int > nodes[MAXN];
vector< int > nodesTin[MAXN];
vector< int > ansHeavy[MAXN];

void DFSInit(int cur)
{
	tin[cur] = ++curTime;

	for(int i = 0 ; i < adj[cur].size() ; i++)
		DFSInit( adj[cur][i] );

	tout[cur] = curTime;
}

void DFSCalculate(int cur, int heavyRegion)
{
	if( v[cur] == heavyRegion )
		prof[cur]++;

	for(int i = 0 ; i < adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];
		
		prof[viz] = prof[cur];

		DFSCalculate( viz , heavyRegion );
	}
}

int lightQuery(int A, int B)
{
	int ans = 0;

	for(int i = 0 ; i < nodes[A].size() ; i++)
	{
		int L = tin[ nodes[A][i] ];
		int R = tout[ nodes[A][i] ];

		auto itL = lower_bound( nodesTin[B].begin() , nodesTin[B].end() , L );
		auto itR = upper_bound( nodesTin[B].begin() , nodesTin[B].end() , R );

		ans += itR - itL;
	}

	return ans;
}

int main()
{
	scanf("%d %d %d",&n,&r,&q);

	int T = sqrt( 4*r ) + 1;

	scanf("%d",&v[1]);

	for(int i = 2 ; i <= n ; i++)
	{
		int p;
		scanf("%d %d",&p,&v[i]);

		adj[p].push_back( i );
	}

	DFSInit( 1 );

	for(int i = 1 ; i <= n ; i++)
	{
		nodes[ v[i] ].push_back( i );
		nodesTin[ v[i] ].push_back( tin[i] );
	}

	for(int i = 1 ; i <= r ; i++)
		sort( nodesTin[i].begin() , nodesTin[i].end() );

	int curInd = 0;

	for(int i = 1 ; i <= r ; i++)
	{
		if( nodes[i].size() < T ) continue;

		isHeavy[i] = true;
		indHeavy[i] = ++curInd;

		prof[1] = 0;
		DFSCalculate( 1 , i );

		for(int j = 1 ; j <= n ; j++)
			upAnswer[ v[j] ] += prof[j];

		for(int j = 1 ; j <= r ; j++)
			ansHeavy[curInd].push_back( upAnswer[j] );

		for(int j = 1 ; j <= r ; j++)
			upAnswer[j] = 0;
	}

	for(int i = 1 ; i <= q ; i++)
	{
		int A, B;
		scanf("%d %d",&A,&B);

		if( !isHeavy[A] ) printf("%d\n",lightQuery( A , B ));
		else
		{
			int ind = indHeavy[A];
			printf("%d\n",ansHeavy[ind][B - 1]);
		}

		fflush( stdout );
	}
}

Compilation message

regions.cpp: In function 'void DFSInit(int)':
regions.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
regions.cpp: In function 'void DFSCalculate(int, int)':
regions.cpp:43:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
regions.cpp: In function 'int lightQuery(int, int)':
regions.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < nodes[A].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:102:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if( nodes[i].size() < T ) continue;
       ~~~~~~~~~~~~~~~~^~~
regions.cpp:73: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:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&v[1]);
  ~~~~~^~~~~~~~~~~~
regions.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&p,&v[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp:123:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&A,&B);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19120 KB Output is correct
2 Correct 15 ms 19200 KB Output is correct
3 Correct 21 ms 19072 KB Output is correct
4 Correct 19 ms 19072 KB Output is correct
5 Correct 25 ms 19200 KB Output is correct
6 Correct 47 ms 19200 KB Output is correct
7 Correct 63 ms 19200 KB Output is correct
8 Correct 54 ms 19200 KB Output is correct
9 Correct 87 ms 19584 KB Output is correct
10 Correct 122 ms 19712 KB Output is correct
11 Correct 235 ms 20484 KB Output is correct
12 Correct 278 ms 21112 KB Output is correct
13 Correct 433 ms 21040 KB Output is correct
14 Correct 393 ms 21036 KB Output is correct
15 Correct 371 ms 23672 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1382 ms 24364 KB Output is correct
2 Correct 1684 ms 23288 KB Output is correct
3 Correct 1647 ms 26360 KB Output is correct
4 Correct 334 ms 22648 KB Output is correct
5 Correct 450 ms 22008 KB Output is correct
6 Correct 684 ms 24272 KB Output is correct
7 Correct 1335 ms 25788 KB Output is correct
8 Correct 1214 ms 32888 KB Output is correct
9 Correct 2884 ms 35960 KB Output is correct
10 Correct 3364 ms 44604 KB Output is correct
11 Correct 5825 ms 32188 KB Output is correct
12 Correct 1653 ms 30788 KB Output is correct
13 Correct 2191 ms 31020 KB Output is correct
14 Correct 2668 ms 32632 KB Output is correct
15 Correct 3712 ms 35364 KB Output is correct
16 Correct 3403 ms 40696 KB Output is correct
17 Correct 3182 ms 41240 KB Output is correct