oj.uz

Submission #116393

# Submission time Handle Problem Language Result Execution time Memory
116393 2019-06-12T11:36:11 Z kig9981 Regions (IOI09_regions) C++17
30 / 100
 8000 ms 119772 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], PS[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]++;
		PS[idx][num[c]]++;
	}
	for(auto n: adj[c]) {
		sum[idx][n]=sum[idx][c];
		dfs2(n,idx);
	}
}

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[i]) ans[O.size()-1][O[j]].first+=sum[j][r];
			for(auto r: R[O[j]]) ans[j][O.back()].first+=sum[O.size()-1][r];
		}
	}
	for(int i=0;i<O.size();i++) {
		for(int j=1;j<N;j++) PS[i][j]+=PS[i][j-1];
		for(int j=0;j<M;j++) if(R[j].size()<rt) for(auto r: R[j]) {
			ans[i][j].first+=PS[i][fin[r]]-(num[r] ? PS[i][num[r]-1]:0);
			ans[i][j].second+=sum[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:73:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<O.size()-1;j++) {
               ~^~~~~~~~~~~
regions.cpp:78: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 9 ms 5760 KB Output is correct
4 Correct 13 ms 5760 KB Output is correct
5 Correct 10 ms 5760 KB Output is correct
6 Correct 22 ms 5712 KB Output is correct
7 Correct 27 ms 5632 KB Output is correct
8 Correct 43 ms 5760 KB Output is correct
9 Correct 43 ms 6112 KB Output is correct
10 Correct 82 ms 6144 KB Output is correct
11 Correct 146 ms 6400 KB Output is correct
12 Correct 106 ms 6784 KB Output is correct
13 Correct 212 ms 6528 KB Output is correct
14 Correct 443 ms 7040 KB Output is correct
15 Correct 504 ms 8952 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1801 ms 19752 KB Output isn't correct
2 Incorrect 1767 ms 17364 KB Output isn't correct
3 Incorrect 3901 ms 19064 KB Output isn't correct
4 Correct 371 ms 7112 KB Output is correct
5 Correct 532 ms 8356 KB Output is correct
6 Incorrect 644 ms 40216 KB Output isn't correct
7 Incorrect 2339 ms 20740 KB Output isn't correct
8 Incorrect 1761 ms 109560 KB Output isn't correct
9 Correct 5017 ms 14072 KB Output is correct
10 Incorrect 6267 ms 119772 KB Output isn't correct
11 Execution timed out 8066 ms 13944 KB Time limit exceeded
12 Incorrect 2498 ms 19368 KB Output isn't correct
13 Incorrect 3447 ms 19448 KB Output isn't correct
14 Incorrect 4313 ms 57156 KB Output isn't correct
15 Incorrect 6644 ms 23764 KB Output isn't correct
16 Incorrect 6548 ms 29308 KB Output isn't correct
17 Incorrect 5542 ms 67408 KB Output isn't correct