oj.uz

Submission #211917

# Submission time Handle Problem Language Result Execution time Memory
211917 2020-03-21T17:40:14 Z Lawliet Regions (IOI09_regions) C++17
95 / 100
 8000 ms 90936 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( 2*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 15 ms 19072 KB Output is correct
2 Correct 15 ms 19072 KB Output is correct
3 Correct 17 ms 19200 KB Output is correct
4 Correct 19 ms 19072 KB Output is correct
5 Correct 24 ms 19072 KB Output is correct
6 Correct 29 ms 19200 KB Output is correct
7 Correct 42 ms 19200 KB Output is correct
8 Correct 47 ms 19252 KB Output is correct
9 Correct 67 ms 19712 KB Output is correct
10 Correct 106 ms 19832 KB Output is correct
11 Correct 205 ms 20472 KB Output is correct
12 Correct 280 ms 21368 KB Output is correct
13 Correct 385 ms 20856 KB Output is correct
14 Correct 321 ms 21012 KB Output is correct
15 Correct 294 ms 23544 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 993 ms 24312 KB Output is correct
2 Correct 1315 ms 23180 KB Output is correct
3 Correct 1499 ms 26488 KB Output is correct
4 Correct 329 ms 22700 KB Output is correct
5 Correct 389 ms 23672 KB Output is correct
6 Correct 627 ms 24312 KB Output is correct
7 Correct 1155 ms 27160 KB Output is correct
8 Correct 1175 ms 32780 KB Output is correct
9 Correct 2927 ms 35716 KB Output is correct
10 Correct 3412 ms 44408 KB Output is correct
11 Correct 7874 ms 89772 KB Output is correct
12 Execution timed out 8020 ms 59664 KB Time limit exceeded
13 Correct 7457 ms 69704 KB Output is correct
14 Correct 2845 ms 32748 KB Output is correct
15 Correct 3640 ms 35448 KB Output is correct
16 Correct 4563 ms 90936 KB Output is correct
17 Correct 3797 ms 41160 KB Output is correct