oj.uz

Submission #211744

# Submission time Handle Problem Language Result Execution time Memory
211744 2020-03-21T06:33:43 Z Lawliet Regions (IOI09_regions) C++17
25 / 100
 8000 ms 131076 KB 
#include <bits/stdc++.h>

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

const int MAXN = 200010;

class FenwickTree
{
	public:

		void update(int i, int v)
		{
			for( ; i < MAXN ; i += i & -i )
				BIT[i] += v;
		}

		int query(int i)
		{
			int ans = 0;

			for( ; i > 0 ; i -= i & -i )
				ans += BIT[i];

			return ans;
		}

		int sum(int L, int R) { return query(R) - query(L - 1); }

		FenwickTree() { memset( BIT , 0 , sizeof(BIT) ); }

	private:

		int BIT[MAXN];
};

int n, r, q;
int curTime;

int v[MAXN];
int freq[MAXN];

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

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

bool isHeavy[MAXN];

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

FenwickTree BIT;

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)
{
	sub[cur] = 0;

	if( v[cur] == heavyRegion )
	{
		sub[cur]++;
		prof[cur]++;
	}

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

		DFSCalculate( viz , heavyRegion );

		sub[cur] += sub[viz];
	}
}

int lightQuery(int A, int B)
{
	for(int i = 0 ; i < nodes[B].size() ; i++)
		BIT.update( tin[ nodes[B][i] ] , 1 );

	int ans = 0;

	for(int i = 0 ; i < nodes[A].size() ; i++)
		ans += BIT.sum( tin[ nodes[A][i] ] , tout[ nodes[A][i] ] );

	for(int i = 0 ; i < nodes[B].size() ; i++)
		BIT.update( tin[ nodes[B][i] ] , -1 );

	return ans;
}

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

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

	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 );
	}

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

	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];
			downAnswer[ v[j] ] += sub[j];
		}

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

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

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

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

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

		fflush( stdout );
	}
}

Compilation message

regions.cpp: In function 'void DFSInit(int)':
regions.cpp:65: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:81: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:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < nodes[B].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
regions.cpp:100:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < nodes[A].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
regions.cpp:103:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < nodes[B].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:111: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:118:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&v[1]);
  ~~~~~^~~~~~~~~~~~
regions.cpp:123: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:165: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
10.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15232 KB Output is correct
2 Correct 13 ms 15232 KB Output is correct
3 Execution timed out 8057 ms 15232 KB Time limit exceeded
4 Execution timed out 8071 ms 15232 KB Time limit exceeded
5 Correct 21 ms 15232 KB Output is correct
6 Execution timed out 8071 ms 15360 KB Time limit exceeded
7 Execution timed out 8066 ms 15616 KB Time limit exceeded
8 Execution timed out 8092 ms 15744 KB Time limit exceeded
9 Correct 80 ms 17016 KB Output is correct
10 Correct 209 ms 17400 KB Output is correct
11 Correct 220 ms 17016 KB Output is correct
12 Correct 287 ms 18296 KB Output is correct
13 Correct 407 ms 17400 KB Output is correct
14 Correct 335 ms 17052 KB Output is correct
15 Correct 348 ms 19600 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1848 ms 19984 KB Output is correct
2 Correct 1903 ms 18680 KB Output is correct
3 Correct 2197 ms 22136 KB Output is correct
4 Execution timed out 8032 ms 19960 KB Time limit exceeded
5 Execution timed out 8044 ms 35584 KB Time limit exceeded
6 Execution timed out 8036 ms 21372 KB Time limit exceeded
7 Execution timed out 8053 ms 29512 KB Time limit exceeded
8 Execution timed out 8035 ms 56056 KB Time limit exceeded
9 Execution timed out 8096 ms 95992 KB Time limit exceeded
10 Runtime error 2206 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 6501 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Execution timed out 8038 ms 79028 KB Time limit exceeded
13 Execution timed out 8029 ms 102720 KB Time limit exceeded
14 Execution timed out 8087 ms 99800 KB Time limit exceeded
15 Runtime error 3306 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 2863 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Execution timed out 8083 ms 117640 KB Time limit exceeded