oj.uz

Submission #211915

# Submission time Handle Problem Language Result Execution time Memory
211915 2020-03-21T17:24:49 Z Lawliet Regions (IOI09_regions) C++17
27 / 100
 8000 ms 89588 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 freq[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 > 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( nodes[B].begin() , nodes[B].end() , L );
		auto itR = upper_bound( nodes[B].begin() , nodes[B].end() , R );

		ans += itR - itL;
	}

	return ans;
}

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

	double aux = r;
	aux /= log2( n );

	int T = sqrt( aux ) + 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++)
	{
		freq[ v[i] ]++;
		nodes[ v[i] ].push_back( tin[i] );
	}

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

	int curInd = 0;

	for(int i = 1 ; i <= r ; i++)
	{
		if( freq[i] < 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: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:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&v[1]);
  ~~~~~^~~~~~~~~~~~
regions.cpp:85: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:126: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
12.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14464 KB Output is correct
2 Correct 12 ms 14336 KB Output is correct
3 Incorrect 14 ms 14464 KB Output isn't correct
4 Incorrect 18 ms 14464 KB Output isn't correct
5 Correct 22 ms 14464 KB Output is correct
6 Correct 31 ms 14464 KB Output is correct
7 Correct 43 ms 14720 KB Output is correct
8 Incorrect 59 ms 14772 KB Output isn't correct
9 Correct 71 ms 15480 KB Output is correct
10 Correct 197 ms 15748 KB Output is correct
11 Correct 225 ms 15736 KB Output is correct
12 Correct 296 ms 16632 KB Output is correct
13 Correct 425 ms 16120 KB Output is correct
14 Correct 318 ms 16120 KB Output is correct
15 Correct 304 ms 18680 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1129 ms 19124 KB Output is correct
2 Correct 1264 ms 18040 KB Output is correct
3 Correct 1548 ms 21368 KB Output is correct
4 Incorrect 366 ms 17784 KB Output isn't correct
5 Incorrect 507 ms 27128 KB Output isn't correct
6 Incorrect 607 ms 19100 KB Output isn't correct
7 Incorrect 1051 ms 24056 KB Output isn't correct
8 Incorrect 1526 ms 40756 KB Output isn't correct
9 Incorrect 6950 ms 64880 KB Output isn't correct
10 Incorrect 3488 ms 88668 KB Output isn't correct
11 Incorrect 7801 ms 83808 KB Output isn't correct
12 Execution timed out 8085 ms 54564 KB Time limit exceeded
13 Incorrect 7458 ms 64004 KB Output isn't correct
14 Execution timed out 8026 ms 67068 KB Time limit exceeded
15 Incorrect 4897 ms 89588 KB Output isn't correct
16 Incorrect 4107 ms 85128 KB Output isn't correct
17 Incorrect 3915 ms 75584 KB Output isn't correct