oj.uz

Submission #116423

# Submission time Handle Problem Language Result Execution time Memory
116423 2019-06-12T12:41:55 Z kig9981 Regions (IOI09_regions) C++17
95 / 100
 8000 ms 82176 KB 
#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;

const int rt=448;
vector<int> adj[200000], R[25000], O;
int node_cnt=-1, RV[200000], num[200000], fin[200000], sum[rt][200000], tree[200001], idx[200000];
long long ans1[rt][25000], ans2[rt][25000];

void add_tree(int n, int v)
{
	for(++n;n<=200000;n+=n&-n) tree[n]+=v;
}

int get_sum(int n)
{
	int ret=0;
	for(++n;n;n-=n&-n) ret+=tree[n];
	return ret;
}

int get_sum(int s, int e)
{
	return get_sum(e)-get_sum(s-1);
}

void dfs(int c)
{
	num[c]=++node_cnt;
	for(auto n: adj[c]) dfs(n);
	fin[c]=node_cnt;
}

void dfs2(int c, int idx)
{
	sum[idx][c]+=RV[c]==O[idx];
	for(auto n: adj[c]) {
		sum[idx][n]=sum[idx][c];
		dfs2(n,idx);
	}
}

void dfs3(int c, int idx)
{
	sum[idx][c]=RV[c]==O[idx];
	for(auto n: adj[c]) {
		dfs3(n,idx);
		sum[idx][c]+=sum[idx][n];
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, M, Q, p;
	cin>>N>>M>>Q>>RV[0];
	R[--RV[0]].push_back(0);
	for(int i=1;i<N;i++) {
		cin>>p>>RV[i];
		adj[--p].push_back(i);
		R[--RV[i]].push_back(i);
	}
	dfs(0);
	for(int i=0;i<M;i++) if(R[i].size()>=rt) {
		idx[i]=O.size();
		O.push_back(i);
		dfs2(0,O.size()-1);
	}
	for(int i=0;i<O.size();i++) {
		for(int j=0;j<N;j++) ans1[i][RV[j]]+=sum[i][j];
		dfs3(0,i);
		for(int j=0;j<N;j++) ans2[i][RV[j]]+=sum[i][j];
	}
	
	while(Q--) {
		int a, b;
		cin>>a>>b; --a; --b;
		if(R[a].size()>=rt) cout<<ans1[idx[a]][b]<<'\n';
		else if(R[b].size()>=rt) cout<<ans2[idx[b]][a]<<'\n';
		else {
			long long ans=0;
			for(auto r: R[b]) add_tree(num[r],1);
			for(auto r: R[a]) ans+=get_sum(num[r],fin[r]);
			for(auto r: R[b]) add_tree(num[r],-1);
			cout<<ans<<'\n';
		}
		cout.flush();
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:81:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<O.size();i++) {
              ~^~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5632 KB Output is correct
2 Correct 6 ms 5632 KB Output is correct
3 Correct 7 ms 5632 KB Output is correct
4 Correct 10 ms 5632 KB Output is correct
5 Correct 17 ms 5760 KB Output is correct
6 Correct 20 ms 5760 KB Output is correct
7 Correct 49 ms 5680 KB Output is correct
8 Correct 41 ms 5760 KB Output is correct
9 Correct 67 ms 6144 KB Output is correct
10 Correct 91 ms 6272 KB Output is correct
11 Correct 169 ms 6528 KB Output is correct
12 Correct 158 ms 6784 KB Output is correct
13 Correct 215 ms 6576 KB Output is correct
14 Correct 506 ms 7040 KB Output is correct
15 Correct 544 ms 9080 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1937 ms 15304 KB Output is correct
2 Correct 1876 ms 13304 KB Output is correct
3 Correct 3679 ms 16120 KB Output is correct
4 Correct 415 ms 7164 KB Output is correct
5 Correct 580 ms 8448 KB Output is correct
6 Correct 788 ms 28132 KB Output is correct
7 Correct 2224 ms 16504 KB Output is correct
8 Correct 1681 ms 71520 KB Output is correct
9 Correct 5091 ms 14044 KB Output is correct
10 Correct 6212 ms 82176 KB Output is correct
11 Execution timed out 8041 ms 13944 KB Time limit exceeded
12 Correct 2315 ms 17804 KB Output is correct
13 Correct 3386 ms 18296 KB Output is correct
14 Correct 5360 ms 40180 KB Output is correct
15 Correct 6398 ms 23328 KB Output is correct
16 Correct 5944 ms 30584 KB Output is correct
17 Correct 5645 ms 52256 KB Output is correct