Submission #94261

# Submission time Handle Problem Language Result Execution time Memory
94261 2019-01-17T08:10:01 Z hamzqq9 Regions (IOI09_regions) C++14
0 / 100
1359 ms 76448 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));

		}

	}

}

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 Execution timed out 6 ms 6136 KB Time limit exceeded (wall clock)
2 Execution timed out 6 ms 6264 KB Time limit exceeded (wall clock)
3 Execution timed out 6 ms 6136 KB Time limit exceeded (wall clock)
4 Execution timed out 6 ms 6136 KB Time limit exceeded (wall clock)
5 Execution timed out 6 ms 6264 KB Time limit exceeded (wall clock)
6 Execution timed out 6 ms 6248 KB Time limit exceeded (wall clock)
7 Execution timed out 7 ms 6200 KB Time limit exceeded (wall clock)
8 Execution timed out 7 ms 6264 KB Time limit exceeded (wall clock)
9 Execution timed out 8 ms 6776 KB Time limit exceeded (wall clock)
10 Execution timed out 9 ms 6904 KB Time limit exceeded (wall clock)
11 Execution timed out 12 ms 7204 KB Time limit exceeded (wall clock)
12 Execution timed out 15 ms 7928 KB Time limit exceeded (wall clock)
13 Execution timed out 17 ms 7800 KB Time limit exceeded (wall clock)
14 Execution timed out 20 ms 8568 KB Time limit exceeded (wall clock)
15 Execution timed out 23 ms 11256 KB Time limit exceeded (wall clock)
# Verdict Execution time Memory Grader output
1 Execution timed out 96 ms 12024 KB Time limit exceeded (wall clock)
2 Execution timed out 95 ms 10920 KB Time limit exceeded (wall clock)
3 Execution timed out 70 ms 14584 KB Time limit exceeded (wall clock)
4 Execution timed out 21 ms 8360 KB Time limit exceeded (wall clock)
5 Execution timed out 23 ms 10148 KB Time limit exceeded (wall clock)
6 Execution timed out 234 ms 23660 KB Time limit exceeded (wall clock)
7 Execution timed out 129 ms 29816 KB Time limit exceeded (wall clock)
8 Execution timed out 450 ms 38840 KB Time limit exceeded (wall clock)
9 Execution timed out 84 ms 18680 KB Time limit exceeded (wall clock)
10 Execution timed out 798 ms 73640 KB Time limit exceeded (wall clock)
11 Execution timed out 108 ms 18868 KB Time limit exceeded (wall clock)
12 Execution timed out 292 ms 48120 KB Time limit exceeded (wall clock)
13 Execution timed out 205 ms 48404 KB Time limit exceeded (wall clock)
14 Execution timed out 1359 ms 56012 KB Time limit exceeded (wall clock)
15 Execution timed out 183 ms 69496 KB Time limit exceeded (wall clock)
16 Execution timed out 163 ms 76448 KB Time limit exceeded (wall clock)
17 Execution timed out 403 ms 67164 KB Time limit exceeded (wall clock)