oj.uz

Submission #116392

# Submission time Handle Problem Language Result Execution time Memory
116392 2019-06-12T11:31:04 Z kig9981 Regions (IOI09_regions) C++17
55 / 100
 8000 ms 119680 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+=sum[i][r];
			ans[i][j].second+=PS[i][fin[r]]-(num[r] ? PS[i][num[r]-1]:0);
		}
	}
	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 7 ms 5760 KB Output is correct
2 Correct 6 ms 5760 KB Output is correct
3 Correct 7 ms 5632 KB Output is correct
4 Correct 11 ms 5632 KB Output is correct
5 Correct 12 ms 5760 KB Output is correct
6 Correct 23 ms 5760 KB Output is correct
7 Correct 37 ms 5760 KB Output is correct
8 Correct 36 ms 5760 KB Output is correct
9 Correct 63 ms 6016 KB Output is correct
10 Correct 81 ms 6144 KB Output is correct
11 Correct 172 ms 6400 KB Output is correct
12 Correct 148 ms 6784 KB Output is correct
13 Correct 283 ms 6528 KB Output is correct
14 Correct 356 ms 7156 KB Output is correct
15 Correct 511 ms 8960 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1707 ms 19704 KB Output isn't correct
2 Incorrect 1874 ms 17272 KB Output isn't correct
3 Incorrect 4030 ms 19072 KB Output isn't correct
4 Correct 406 ms 7168 KB Output is correct
5 Correct 395 ms 8368 KB Output is correct
6 Incorrect 805 ms 40184 KB Output isn't correct
7 Correct 2205 ms 20736 KB Output is correct
8 Correct 1763 ms 109628 KB Output is correct
9 Correct 5246 ms 14248 KB Output is correct
10 Incorrect 5420 ms 119680 KB Output isn't correct
11 Execution timed out 8052 ms 13960 KB Time limit exceeded
12 Correct 2623 ms 19236 KB Output is correct
13 Correct 3565 ms 19448 KB Output is correct
14 Incorrect 4345 ms 57164 KB Output isn't correct
15 Incorrect 6483 ms 23768 KB Output isn't correct
16 Correct 6335 ms 29224 KB Output is correct
17 Incorrect 5490 ms 67504 KB Output isn't correct