oj.uz

Submission #211916

# Submission time Handle Problem Language Result Execution time Memory
211916 2020-03-21T17:38:20 Z Lawliet Regions (IOI09_regions) C++17
90 / 100
 8000 ms 95604 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( 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 14 ms 19072 KB Output is correct
2 Correct 14 ms 19072 KB Output is correct
3 Correct 16 ms 19072 KB Output is correct
4 Correct 20 ms 19072 KB Output is correct
5 Correct 22 ms 19200 KB Output is correct
6 Correct 29 ms 19200 KB Output is correct
7 Correct 40 ms 19200 KB Output is correct
8 Correct 46 ms 19200 KB Output is correct
9 Correct 51 ms 19960 KB Output is correct
10 Correct 167 ms 20332 KB Output is correct
11 Correct 201 ms 20472 KB Output is correct
12 Correct 278 ms 21368 KB Output is correct
13 Correct 391 ms 20856 KB Output is correct
14 Correct 343 ms 21012 KB Output is correct
15 Correct 298 ms 23672 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1006 ms 24184 KB Output is correct
2 Correct 1275 ms 23160 KB Output is correct
3 Correct 1461 ms 26360 KB Output is correct
4 Correct 335 ms 22520 KB Output is correct
5 Correct 400 ms 24952 KB Output is correct
6 Correct 631 ms 24440 KB Output is correct
7 Correct 1098 ms 27896 KB Output is correct
8 Correct 1319 ms 39160 KB Output is correct
9 Correct 6580 ms 67444 KB Output is correct
10 Correct 3481 ms 94968 KB Output is correct
11 Correct 7955 ms 89688 KB Output is correct
12 Execution timed out 8039 ms 60200 KB Time limit exceeded
13 Correct 7353 ms 69596 KB Output is correct
14 Execution timed out 8038 ms 72196 KB Time limit exceeded
15 Correct 4816 ms 95604 KB Output is correct
16 Correct 4143 ms 91044 KB Output is correct
17 Correct 3904 ms 81336 KB Output is correct