Submission #94262

# Submission time Handle Problem Language Result Execution time Memory
94262 2019-01-17T08:14:31 Z hamzqq9 Regions (IOI09_regions) C++14
35 / 100
2855 ms 76432 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) {

	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:107: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:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",c+1);
  ~~~~~^~~~~~~~~~
regions.cpp:113: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:168:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 6 ms 6136 KB Output is correct
2 Correct 6 ms 6264 KB Output is correct
3 Correct 8 ms 6136 KB Output is correct
4 Correct 10 ms 6184 KB Output is correct
5 Correct 14 ms 6136 KB Output is correct
6 Correct 25 ms 6264 KB Output is correct
7 Correct 39 ms 6392 KB Output is correct
8 Correct 36 ms 6264 KB Output is correct
9 Correct 45 ms 6776 KB Output is correct
10 Correct 38 ms 6904 KB Output is correct
11 Correct 95 ms 7292 KB Output is correct
12 Correct 135 ms 7852 KB Output is correct
13 Correct 175 ms 7800 KB Output is correct
14 Correct 90 ms 8436 KB Output is correct
15 Correct 197 ms 11128 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 829 ms 12060 KB Output isn't correct
2 Incorrect 913 ms 10940 KB Output isn't correct
3 Incorrect 1429 ms 14596 KB Output isn't correct
4 Correct 245 ms 8440 KB Output is correct
5 Correct 265 ms 9976 KB Output is correct
6 Incorrect 706 ms 23636 KB Output isn't correct
7 Incorrect 970 ms 29760 KB Output isn't correct
8 Incorrect 1145 ms 38872 KB Output isn't correct
9 Correct 1248 ms 18632 KB Output is correct
10 Incorrect 2258 ms 73660 KB Output isn't correct
11 Correct 2117 ms 18876 KB Output is correct
12 Incorrect 1026 ms 47864 KB Output isn't correct
13 Incorrect 1247 ms 48376 KB Output isn't correct
14 Incorrect 2855 ms 55976 KB Output isn't correct
15 Incorrect 1731 ms 69416 KB Output isn't correct
16 Incorrect 1617 ms 76432 KB Output isn't correct
17 Incorrect 2483 ms 67112 KB Output isn't correct