oj.uz

Submission #121475

# Submission time Handle Problem Language Result Execution time Memory
121475 2019-06-26T14:27:45 Z TadijaSebez Regions (IOI09_regions) C++11
90 / 100
 8000 ms 80260 KB 
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long int
const int N=200050;
const int S=190;
const int H=1060;
const int M=25050;
int sol[H][M];
int hid[M],reg[N],tsz;
vector<int> E[N],My[M],ids[M];
int lid[N],rid[N],tid;
void DFS(int u)
{
	lid[u]=++tid;
	ids[reg[u]].pb(tid);
	for(int i=0;i<E[u].size();i++) DFS(E[u][i]);
	rid[u]=tid;
}
void Heavy(int u, int r, int c)
{
	if(reg[u]==r) c++;
	else sol[hid[r]][reg[u]]+=c;
	for(int i=0;i<E[u].size();i++) Heavy(E[u][i],r,c);
}
int Get(int l, int r, int ty)
{
	return upper_bound(ids[ty].begin(),ids[ty].end(),r)-lower_bound(ids[ty].begin(),ids[ty].end(),l);
}
int par[N];
int main()
{
	int n,m,q,i;
	scanf("%i %i %i",&n,&m,&q);
	scanf("%i",&reg[1]);
	for(i=2;i<=n;i++) scanf("%i %i",&par[i],&reg[i]),E[par[i]].pb(i);
	for(i=1;i<=n;i++) My[reg[i]].pb(i);
	DFS(1);
	for(i=1;i<=m;i++) if(My[i].size()>=S) hid[i]=++tsz,Heavy(1,i,0);
	int x,y;
	while(q--)
	{
		scanf("%i %i",&x,&y);
		if(My[x].size()>=S) printf("%i\n",sol[hid[x]][y]);
		else
		{
			int ans=0;
			for(i=0;i<My[x].size();i++)
			{
				ans+=Get(lid[My[x][i]],rid[My[x][i]],y);
			}
			printf("%i\n",ans);
		}
		fflush(stdout);
	}
	return 0;
}

Compilation message

regions.cpp: In function 'void DFS(int)':
regions.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<E[u].size();i++) DFS(E[u][i]);
              ~^~~~~~~~~~~~
regions.cpp: In function 'void Heavy(int, int, int)':
regions.cpp:27:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<E[u].size();i++) Heavy(E[u][i],r,c);
              ~^~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:51:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<My[x].size();i++)
            ~^~~~~~~~~~~~~
regions.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&m,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&reg[1]);
  ~~~~~^~~~~~~~~~~~~~
regions.cpp:39:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=2;i<=n;i++) scanf("%i %i",&par[i],&reg[i]),E[par[i]].pb(i);
                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
regions.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6144 KB Output is correct
2 Correct 7 ms 6144 KB Output is correct
3 Correct 9 ms 6272 KB Output is correct
4 Correct 10 ms 6272 KB Output is correct
5 Correct 14 ms 6272 KB Output is correct
6 Correct 20 ms 6272 KB Output is correct
7 Correct 45 ms 6272 KB Output is correct
8 Correct 42 ms 6400 KB Output is correct
9 Correct 73 ms 6656 KB Output is correct
10 Correct 89 ms 6784 KB Output is correct
11 Correct 104 ms 7036 KB Output is correct
12 Correct 147 ms 7424 KB Output is correct
13 Correct 196 ms 7296 KB Output is correct
14 Correct 330 ms 7808 KB Output is correct
15 Correct 371 ms 10488 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1315 ms 11736 KB Output is correct
2 Correct 1038 ms 10896 KB Output is correct
3 Correct 1447 ms 14396 KB Output is correct
4 Correct 305 ms 7936 KB Output is correct
5 Correct 361 ms 9216 KB Output is correct
6 Correct 530 ms 11220 KB Output is correct
7 Correct 1075 ms 13304 KB Output is correct
8 Correct 1250 ms 19872 KB Output is correct
9 Correct 2980 ms 22584 KB Output is correct
10 Correct 3314 ms 80260 KB Output is correct
11 Execution timed out 8009 ms 75132 KB Time limit exceeded
12 Execution timed out 8074 ms 32840 KB Time limit exceeded
13 Correct 6754 ms 47580 KB Output is correct
14 Correct 6053 ms 30744 KB Output is correct
15 Correct 4456 ms 55504 KB Output is correct
16 Correct 3689 ms 76568 KB Output is correct
17 Correct 4085 ms 39072 KB Output is correct