oj.uz

Submission #116406

# Submission time Handle Problem Language Result Execution time Memory
116406 2019-06-12T12:05:59 Z kig9981 Regions (IOI09_regions) C++17
95 / 100
 8000 ms 55608 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=1000;
vector<int> adj[200000], R[25000], O;
int node_cnt=-1, RV[200000], num[200000], fin[200000], sum[rt][200000], sum2[rt][200000], tree[200001];
pair<long long,long long> ans[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)
{
	if(RV[c]==O[idx]) {
		sum[idx][c]++;
		sum2[idx][c]++;
	}
	for(auto n: adj[c]) {
		sum[idx][n]=sum[idx][c];
		dfs2(n,idx);
		sum2[idx][c]+=sum2[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) {
		O.push_back(i);
		dfs2(0,O.size()-1);
		for(int j=0;j<O.size()-1;j++) {
			for(auto r: R[O[j]]) ans[O.size()-1][O[j]].first+=sum[O.size()-1][r];
			for(auto r: R[i]) ans[j][i].first+=sum[j][r];
		}
	}
	for(int i=0;i<O.size();i++) {
		for(int j=0;j<M;j++) if(R[j].size()<rt) for(auto r: R[j]) {
			ans[i][j].first+=sum[i][r];
			ans[i][j].second+=sum2[i][r];
		}
	}
	while(Q--) {
		int a, b;
		cin>>a>>b; --a; --b;
		if(R[a].size()>=rt) cout<<ans[lower_bound(O.begin(),O.end(),a)-O.begin()][b].first<<'\n';
		else if(R[b].size()>=rt) cout<<ans[lower_bound(O.begin(),O.end(),b)-O.begin()][a].second<<'\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:74:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<O.size()-1;j++) {
               ~^~~~~~~~~~~
regions.cpp:79: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 7 ms 5632 KB Output is correct
2 Correct 7 ms 5632 KB Output is correct
3 Correct 7 ms 5760 KB Output is correct
4 Correct 8 ms 5760 KB Output is correct
5 Correct 11 ms 5632 KB Output is correct
6 Correct 19 ms 5632 KB Output is correct
7 Correct 29 ms 5632 KB Output is correct
8 Correct 38 ms 5760 KB Output is correct
9 Correct 27 ms 6016 KB Output is correct
10 Correct 75 ms 6144 KB Output is correct
11 Correct 117 ms 6520 KB Output is correct
12 Correct 260 ms 6784 KB Output is correct
13 Correct 192 ms 6528 KB Output is correct
14 Correct 395 ms 7168 KB Output is correct
15 Correct 463 ms 8960 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1987 ms 12456 KB Output is correct
2 Correct 1910 ms 14100 KB Output is correct
3 Correct 3627 ms 20216 KB Output is correct
4 Correct 452 ms 7168 KB Output is correct
5 Correct 585 ms 8448 KB Output is correct
6 Correct 1875 ms 8312 KB Output is correct
7 Correct 2564 ms 9212 KB Output is correct
8 Correct 2695 ms 13176 KB Output is correct
9 Correct 4532 ms 14144 KB Output is correct
10 Correct 7724 ms 17828 KB Output is correct
11 Execution timed out 8064 ms 13944 KB Time limit exceeded
12 Correct 2615 ms 19388 KB Output is correct
13 Correct 2969 ms 20128 KB Output is correct
14 Correct 4153 ms 40508 KB Output is correct
15 Correct 5727 ms 25956 KB Output is correct
16 Correct 5895 ms 35192 KB Output is correct
17 Correct 6054 ms 55608 KB Output is correct