oj.uz

Submission #211748

# Submission time Handle Problem Language Result Execution time Memory
211748 2020-03-21T06:51:37 Z Lawliet Regions (IOI09_regions) C++17
70 / 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);

	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++)
	{
		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];
				assert( ansHeavy[ind].size() > B - 1 );
				printf("%d\n",ansHeavy[ind][B - 1]);
			}
			else
			{
				int ind = indHeavy[B];
				assert( ansHeavy[ind].size() > A - 1 + r );
				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++)
                  ~~^~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from regions.cpp:1:
regions.cpp: In function 'int main()':
regions.cpp:172:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert( ansHeavy[ind].size() > B - 1 );
             ~~~~~~~~~~~~~~~~~~~~~^~~~~~~
regions.cpp:178:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert( ansHeavy[ind].size() > A - 1 + r );
             ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
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:115:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&v[1]);
  ~~~~~^~~~~~~~~~~~
regions.cpp:120: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:164: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 13 ms 15232 KB Output is correct
2 Correct 13 ms 15232 KB Output is correct
3 Correct 14 ms 15232 KB Output is correct
4 Correct 17 ms 15232 KB Output is correct
5 Correct 19 ms 15360 KB Output is correct
6 Correct 29 ms 15360 KB Output is correct
7 Correct 45 ms 15360 KB Output is correct
8 Correct 54 ms 15488 KB Output is correct
9 Correct 69 ms 16256 KB Output is correct
10 Correct 173 ms 17016 KB Output is correct
11 Correct 217 ms 17144 KB Output is correct
12 Correct 319 ms 18296 KB Output is correct
13 Correct 394 ms 17656 KB Output is correct
14 Correct 340 ms 17272 KB Output is correct
15 Correct 316 ms 19960 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1066 ms 20472 KB Output is correct
2 Correct 1295 ms 19232 KB Output is correct
3 Correct 1588 ms 22904 KB Output is correct
4 Correct 328 ms 20228 KB Output is correct
5 Correct 443 ms 23032 KB Output is correct
6 Correct 638 ms 21752 KB Output is correct
7 Correct 1053 ms 27500 KB Output is correct
8 Correct 1397 ms 44104 KB Output is correct
9 Correct 6928 ms 97184 KB Output is correct
10 Runtime error 2172 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 6410 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Execution timed out 8051 ms 81608 KB Time limit exceeded
13 Correct 7837 ms 104004 KB Output is correct
14 Execution timed out 8083 ms 104224 KB Time limit exceeded
15 Runtime error 3235 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 2782 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Correct 4204 ms 118976 KB Output is correct