oj.uz

Submission #116363

# Submission time Handle Problem Language Result Execution time Memory
116363 2019-06-12T10:43:23 Z kig9981 Regions (IOI09_regions) C++17
30 / 100
 8000 ms 131072 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, SZ=1<<18;
vector<int> adj[200000], R[25000], O;
int node_cnt=-1, RV[200000], num[200000], fin[200000], sum[rt][200000], tree[rt+1][2*SZ];
pair<int,int> ans[rt][200000];

void add_tree(int idx, int n, int v)
{
	for(tree[idx][n+=SZ]+=v;n>>=1;) tree[idx][n]=tree[idx][2*n]+tree[idx][2*n+1];
}

int get_sum(int idx, int s, int e)
{
	int ret=0;
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) ret+=tree[idx][s++];
		if(~e&1) ret+=tree[idx][e--];
	}
	return ret;
}

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]++;
		add_tree(idx,num[c],1);
	}
	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=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+=get_sum(i,num[j],fin[j]);
	}
	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<<endl;
		else if(R[b].size()>=rt) cout<<ans[lower_bound(O.begin(),O.end(),b)-O.begin()][a].second<<endl;
		else {
			int ans=0;
			for(auto r: R[b]) add_tree(rt,num[r],1);
			for(auto r: R[a]) ans+=get_sum(rt,num[r],fin[r]);
			for(auto r: R[b]) add_tree(rt,num[r],-1);
			cout<<ans<<endl;
		}
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:71:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<O.size()-1;j++) {
               ~^~~~~~~~~~~
regions.cpp:76:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  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]) {
              ~^~~~~~~~~

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 8 ms 5632 KB Output is correct
4 Correct 11 ms 5760 KB Output is correct
5 Correct 13 ms 5632 KB Output is correct
6 Correct 21 ms 5760 KB Output is correct
7 Correct 42 ms 5680 KB Output is correct
8 Correct 32 ms 5760 KB Output is correct
9 Correct 69 ms 6144 KB Output is correct
10 Correct 84 ms 6272 KB Output is correct
11 Correct 177 ms 6528 KB Output is correct
12 Correct 192 ms 6912 KB Output is correct
13 Correct 261 ms 6656 KB Output is correct
14 Correct 480 ms 7296 KB Output is correct
15 Correct 824 ms 9208 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2803 ms 25660 KB Output isn't correct
2 Incorrect 2192 ms 22396 KB Output isn't correct
3 Incorrect 6125 ms 23408 KB Output isn't correct
4 Correct 514 ms 7296 KB Output is correct
5 Correct 442 ms 8540 KB Output is correct
6 Incorrect 689 ms 52344 KB Output isn't correct
7 Incorrect 3158 ms 24892 KB Output isn't correct
8 Runtime error 376 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Correct 7894 ms 14744 KB Output is correct
10 Runtime error 535 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Execution timed out 8042 ms 14832 KB Time limit exceeded
12 Incorrect 3464 ms 21496 KB Output isn't correct
13 Incorrect 4085 ms 21560 KB Output isn't correct
14 Incorrect 4711 ms 72452 KB Output isn't correct
15 Execution timed out 8068 ms 25812 KB Time limit exceeded
16 Execution timed out 8052 ms 31352 KB Time limit exceeded
17 Execution timed out 8076 ms 83296 KB Time limit exceeded