oj.uz

Submission #94263

# Submission time Handle Problem Language Result Execution time Memory
94263 2019-01-17T08:20:56 Z hamzqq9 Regions (IOI09_regions) C++14
100 / 100
 2840 ms 76460 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ppf pop_front
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)/2)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 1000000000000000000ll
#define MOD 1000000007
#define N 200005
#define M 25005
#define LOG 20
#define KOK 450
#define EPS 0.00001
using namespace std;

int n,r,q,cnt,t,x,y,tot;
int sub[N],be[N],en[N],c[N],fr[M],id[N],has[N];
int ans1[450][M],ans2[M][450];
vector<int> v[N],qu[M];
vector<ii> add[M];

int solve(int x,int y) {

	int j=-1;
	int cur=0;
	int ans=0;

	for(int i=0;i<sz(add[x]);i++) {

		while(j+1<sz(qu[y]) && qu[y][j+1]<add[x][i].st) {

			++j;

			ans+=cur;

		}

		cur+=add[x][i].nd;

	}

	return ans;

}

void dfs2(int node,int ata,int curid) {

	sub[node]=0;

	for(int i:v[node]) {

		dfs2(i,node,curid);

		sub[node]+=sub[i];		

	}
	
	ans2[c[node]][curid]+=sub[node];

	sub[node]+=(c[node]==has[curid]);

}

void dfs1(int node,int ata,int curid) {

	ans1[curid][c[node]]+=cnt;

	cnt+=(c[node]==has[curid]);

	for(int i:v[node]) {

		dfs1(i,node,curid);

	}

	cnt-=(c[node]==has[curid]);

} 

void dfs(int node,int ata) {

	be[node]=++t;

	for(int i:v[node]) dfs(i,node);

	en[node]=t;

}

int main() {

	//freopen("regions.gir","r",stdin);
	//freopen("regions.cik","w",stdout);

	//freopen("input.txt","r",stdin);

	scanf("%d %d %d",&n,&r,&q);

	scanf("%d",c+1);

	for(int i=2;i<=n;i++) {

		scanf("%d %d",&x,c+i);

		v[x].pb(i);

	}

	dfs(1,0);

	for(int i=1;i<=n;i++) {

		fr[c[i]]++;

	}

	for(int i=1;i<=r;i++) {

		if(fr[i]>=KOK) {

			has[++tot]=i;

			id[i]=tot;

		}

	}

	for(int i=1;i<=n;i++) {

		if(fr[c[i]]<KOK) {

			qu[c[i]].pb(be[i]);

			add[c[i]].pb({be[i]+1,1});
			add[c[i]].pb({en[i]+1,-1});

		}

	}

	for(int i=1;i<=r;i++) {

		sort(all(qu[i]));
		sort(all(add[i]));

	}

	for(int i=1;i<=tot;i++) {

		dfs1(1,0,i);
		dfs2(1,0,i);

	}

	while(q--) {

		scanf("%d %d",&x,&y);

		if(fr[x]>=KOK) {

			printf("%d\n",ans1[id[x]][y]);

		} 
		else if(fr[y]>=KOK) {

			printf("%d\n",ans2[x][id[y]]);

		}
		else {

			printf("%d\n",solve(x,y));

		}

		fflush(stdout);

	}

}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:109: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:111:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",c+1);
  ~~~~~^~~~~~~~~~
regions.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,c+i);
   ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:170:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6136 KB Output is correct
2 Correct 6 ms 6136 KB Output is correct
3 Correct 9 ms 6264 KB Output is correct
4 Correct 11 ms 6136 KB Output is correct
5 Correct 14 ms 6136 KB Output is correct
6 Correct 23 ms 6264 KB Output is correct
7 Correct 17 ms 6392 KB Output is correct
8 Correct 21 ms 6392 KB Output is correct
9 Correct 42 ms 6904 KB Output is correct
10 Correct 74 ms 6908 KB Output is correct
11 Correct 105 ms 7292 KB Output is correct
12 Correct 132 ms 7928 KB Output is correct
13 Correct 147 ms 7672 KB Output is correct
14 Correct 182 ms 8444 KB Output is correct
15 Correct 226 ms 11128 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 12152 KB Output is correct
2 Correct 828 ms 11000 KB Output is correct
3 Correct 1302 ms 14584 KB Output is correct
4 Correct 234 ms 8440 KB Output is correct
5 Correct 337 ms 9976 KB Output is correct
6 Correct 718 ms 23612 KB Output is correct
7 Correct 1012 ms 29824 KB Output is correct
8 Correct 1120 ms 38864 KB Output is correct
9 Correct 1504 ms 18552 KB Output is correct
10 Correct 1883 ms 73776 KB Output is correct
11 Correct 1962 ms 18936 KB Output is correct
12 Correct 1194 ms 48120 KB Output is correct
13 Correct 1218 ms 48412 KB Output is correct
14 Correct 2840 ms 56144 KB Output is correct
15 Correct 2118 ms 69368 KB Output is correct
16 Correct 1905 ms 76460 KB Output is correct
17 Correct 2422 ms 67060 KB Output is correct