oj.uz

Submission #211747

# Submission time Handle Problem Language Result Execution time Memory
211747 2020-03-21T06:48:15 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);

	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( 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:175:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert( ansHeavy[ind].size() > B - 1 );
             ~~~~~~~~~~~~~~~~~~~~~^~~~~~~
regions.cpp:181: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: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:167: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 12 ms 15232 KB Output is correct
3 Correct 14 ms 15232 KB Output is correct
4 Correct 16 ms 15232 KB Output is correct
5 Correct 18 ms 15232 KB Output is correct
6 Correct 29 ms 15232 KB Output is correct
7 Correct 48 ms 15616 KB Output is correct
8 Correct 53 ms 15744 KB Output is correct
9 Correct 81 ms 16888 KB Output is correct
10 Correct 208 ms 17368 KB Output is correct
11 Correct 218 ms 17144 KB Output is correct
12 Correct 290 ms 18328 KB Output is correct
13 Correct 404 ms 17656 KB Output is correct
14 Correct 342 ms 17272 KB Output is correct
15 Correct 316 ms 19832 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1076 ms 20344 KB Output is correct
2 Correct 1367 ms 19320 KB Output is correct
3 Correct 1616 ms 23032 KB Output is correct
4 Correct 321 ms 20088 KB Output is correct
5 Correct 556 ms 35832 KB Output is correct
6 Correct 601 ms 21880 KB Output is correct
7 Correct 1070 ms 30200 KB Output is correct
8 Correct 1608 ms 56788 KB Output is correct
9 Correct 7544 ms 104352 KB Output is correct
10 Runtime error 2271 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 6472 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Execution timed out 8048 ms 81472 KB Time limit exceeded
13 Correct 7801 ms 104412 KB Output is correct
14 Execution timed out 8039 ms 101984 KB Time limit exceeded
15 Runtime error 3284 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 2891 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Correct 4198 ms 119168 KB Output is correct