oj.uz

Submission #116374

# Submission time Handle Problem Language Result Execution time Memory
116374 2019-06-12T10:59:49 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<long long,long long> ans[rt][25000];

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<<'\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(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<<'\n';
		}
		cout.flush();
	}
	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 5804 KB Output is correct
2 Correct 7 ms 5760 KB Output is correct
3 Correct 9 ms 5632 KB Output is correct
4 Correct 11 ms 5632 KB Output is correct
5 Correct 14 ms 5676 KB Output is correct
6 Correct 19 ms 5760 KB Output is correct
7 Correct 32 ms 5680 KB Output is correct
8 Correct 28 ms 5896 KB Output is correct
9 Correct 46 ms 6144 KB Output is correct
10 Correct 113 ms 6272 KB Output is correct
11 Correct 135 ms 6448 KB Output is correct
12 Correct 149 ms 6944 KB Output is correct
13 Correct 222 ms 6656 KB Output is correct
14 Correct 456 ms 7288 KB Output is correct
15 Correct 884 ms 9216 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2263 ms 25552 KB Output isn't correct
2 Incorrect 2459 ms 22300 KB Output isn't correct
3 Incorrect 6638 ms 23428 KB Output isn't correct
4 Correct 558 ms 7216 KB Output is correct
5 Correct 733 ms 8576 KB Output is correct
6 Incorrect 877 ms 55416 KB Output isn't correct
7 Incorrect 3475 ms 26104 KB Output isn't correct
8 Runtime error 458 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Correct 7746 ms 14760 KB Output is correct
10 Runtime error 618 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Execution timed out 8047 ms 14756 KB Time limit exceeded
12 Incorrect 3496 ms 21640 KB Output isn't correct
13 Incorrect 4611 ms 21772 KB Output isn't correct
14 Incorrect 5818 ms 75568 KB Output isn't correct
15 Execution timed out 8034 ms 26236 KB Time limit exceeded
16 Execution timed out 8003 ms 31772 KB Time limit exceeded
17 Execution timed out 8026 ms 86840 KB Time limit exceeded