oj.uz

Submission #116403

# Submission time Handle Problem Language Result Execution time Memory
116403 2019-06-12T12:00:55 Z kig9981 Regions (IOI09_regions) C++17
90 / 100
 8000 ms 72612 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=500;
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 5760 KB Output is correct
2 Correct 6 ms 5632 KB Output is correct
3 Correct 8 ms 5760 KB Output is correct
4 Correct 11 ms 5760 KB Output is correct
5 Correct 9 ms 5712 KB Output is correct
6 Correct 12 ms 5744 KB Output is correct
7 Correct 32 ms 5632 KB Output is correct
8 Correct 38 ms 5804 KB Output is correct
9 Correct 45 ms 6016 KB Output is correct
10 Correct 96 ms 6144 KB Output is correct
11 Correct 102 ms 6400 KB Output is correct
12 Correct 148 ms 6784 KB Output is correct
13 Correct 242 ms 6528 KB Output is correct
14 Correct 404 ms 7160 KB Output is correct
15 Correct 447 ms 8952 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1821 ms 17832 KB Output is correct
2 Correct 2019 ms 17456 KB Output is correct
3 Correct 3705 ms 20216 KB Output is correct
4 Correct 360 ms 7168 KB Output is correct
5 Correct 363 ms 8356 KB Output is correct
6 Correct 1383 ms 18680 KB Output is correct
7 Correct 2720 ms 9284 KB Output is correct
8 Correct 2801 ms 19240 KB Output is correct
9 Correct 4718 ms 14160 KB Output is correct
10 Execution timed out 8047 ms 17800 KB Time limit exceeded
11 Execution timed out 8047 ms 13916 KB Time limit exceeded
12 Correct 2491 ms 19436 KB Output is correct
13 Correct 3422 ms 20056 KB Output is correct
14 Correct 4581 ms 57464 KB Output is correct
15 Correct 5500 ms 25948 KB Output is correct
16 Correct 5641 ms 35320 KB Output is correct
17 Correct 5853 ms 72612 KB Output is correct