oj.uz

Submission #211742

# Submission time Handle Problem Language Result Execution time Memory
211742 2020-03-21T06:32:00 Z Lawliet Regions (IOI09_regions) C++17
15 / 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 = n;
	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 );
	}

	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
5.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15232 KB Output is correct
2 Execution timed out 8039 ms 15232 KB Time limit exceeded
3 Execution timed out 8047 ms 15232 KB Time limit exceeded
4 Execution timed out 8048 ms 15232 KB Time limit exceeded
5 Execution timed out 8090 ms 15360 KB Time limit exceeded
6 Execution timed out 8053 ms 15232 KB Time limit exceeded
7 Execution timed out 8031 ms 15412 KB Time limit exceeded
8 Execution timed out 8042 ms 15360 KB Time limit exceeded
9 Execution timed out 8061 ms 15872 KB Time limit exceeded
10 Execution timed out 8061 ms 16128 KB Time limit exceeded
11 Correct 222 ms 17144 KB Output is correct
12 Execution timed out 8045 ms 18040 KB Time limit exceeded
13 Correct 404 ms 17400 KB Output is correct
14 Correct 331 ms 17016 KB Output is correct
15 Correct 320 ms 19576 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1039 ms 19832 KB Output is correct
2 Execution timed out 8048 ms 18556 KB Time limit exceeded
3 Correct 1556 ms 22264 KB Output is correct
4 Execution timed out 8042 ms 19884 KB Time limit exceeded
5 Execution timed out 8055 ms 29612 KB Time limit exceeded
6 Execution timed out 8051 ms 21368 KB Time limit exceeded
7 Execution timed out 8087 ms 28148 KB Time limit exceeded
8 Execution timed out 8093 ms 55928 KB Time limit exceeded
9 Execution timed out 8101 ms 95904 KB Time limit exceeded
10 Runtime error 2426 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 6934 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Execution timed out 8026 ms 77200 KB Time limit exceeded
13 Execution timed out 8077 ms 102760 KB Time limit exceeded
14 Execution timed out 8067 ms 100024 KB Time limit exceeded
15 Runtime error 3381 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 2849 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Execution timed out 8054 ms 117584 KB Time limit exceeded