oj.uz

Submission #121481

# Submission time Handle Problem Language Result Execution time Memory
121481 2019-06-26T14:33:03 Z TadijaSebez Regions (IOI09_regions) C++11
100 / 100
 6646 ms 31120 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=317;
const int H=635;
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 10 ms 6192 KB Output is correct
4 Correct 9 ms 6272 KB Output is correct
5 Correct 10 ms 6144 KB Output is correct
6 Correct 19 ms 6272 KB Output is correct
7 Correct 29 ms 6272 KB Output is correct
8 Correct 53 ms 6272 KB Output is correct
9 Correct 57 ms 6656 KB Output is correct
10 Correct 106 ms 6784 KB Output is correct
11 Correct 89 ms 7040 KB Output is correct
12 Correct 155 ms 7472 KB Output is correct
13 Correct 177 ms 7296 KB Output is correct
14 Correct 277 ms 7804 KB Output is correct
15 Correct 265 ms 9836 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1828 ms 11220 KB Output is correct
2 Correct 2163 ms 10024 KB Output is correct
3 Correct 3443 ms 13032 KB Output is correct
4 Correct 244 ms 7948 KB Output is correct
5 Correct 390 ms 9216 KB Output is correct
6 Correct 662 ms 11184 KB Output is correct
7 Correct 1339 ms 12408 KB Output is correct
8 Correct 1136 ms 19836 KB Output is correct
9 Correct 3045 ms 16760 KB Output is correct
10 Correct 3465 ms 31120 KB Output is correct
11 Correct 6646 ms 18996 KB Output is correct
12 Correct 1785 ms 17720 KB Output is correct
13 Correct 2039 ms 17856 KB Output is correct
14 Correct 3573 ms 19516 KB Output is correct
15 Correct 3684 ms 22272 KB Output is correct
16 Correct 3620 ms 27512 KB Output is correct
17 Correct 3340 ms 28096 KB Output is correct