oj.uz

Submission #116400

# Submission time Handle Problem Language Result Execution time Memory
116400 2019-06-12T11:53:47 Z kig9981 Regions (IOI09_regions) C++17
55 / 100
 8000 ms 122432 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], 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[i]) ans[O.size()-1][O[j]].first+=sum[O.size()-1][r];
			for(auto r: R[O[j]]) 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 7 ms 5760 KB Output is correct
3 Correct 9 ms 5632 KB Output is correct
4 Correct 10 ms 5760 KB Output is correct
5 Correct 12 ms 5632 KB Output is correct
6 Correct 24 ms 5632 KB Output is correct
7 Correct 45 ms 5760 KB Output is correct
8 Correct 20 ms 5760 KB Output is correct
9 Correct 51 ms 6196 KB Output is correct
10 Correct 95 ms 6272 KB Output is correct
11 Correct 141 ms 6356 KB Output is correct
12 Correct 183 ms 6784 KB Output is correct
13 Correct 245 ms 6576 KB Output is correct
14 Correct 421 ms 7040 KB Output is correct
15 Correct 474 ms 9004 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1526 ms 20236 KB Output isn't correct
2 Incorrect 1859 ms 17400 KB Output isn't correct
3 Incorrect 3704 ms 20216 KB Output isn't correct
4 Correct 463 ms 7152 KB Output is correct
5 Correct 508 ms 8448 KB Output is correct
6 Incorrect 575 ms 40360 KB Output isn't correct
7 Correct 2193 ms 20856 KB Output is correct
8 Correct 1582 ms 111772 KB Output is correct
9 Correct 5075 ms 14156 KB Output is correct
10 Incorrect 5780 ms 122432 KB Output isn't correct
11 Execution timed out 8007 ms 14072 KB Time limit exceeded
12 Correct 2613 ms 19468 KB Output is correct
13 Correct 3237 ms 20076 KB Output is correct
14 Incorrect 4452 ms 57336 KB Output isn't correct
15 Incorrect 6004 ms 25924 KB Output isn't correct
16 Correct 5849 ms 35244 KB Output is correct
17 Incorrect 4951 ms 72616 KB Output isn't correct