oj.uz

Submission #116385

# Submission time Handle Problem Language Result Execution time Memory
116385 2019-06-12T11:22:34 Z kig9981 Regions (IOI09_regions) C++17
45 / 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[r],fin[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(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 7 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 8 ms 5760 KB Output is correct
5 Correct 14 ms 5632 KB Output is correct
6 Correct 24 ms 5760 KB Output is correct
7 Correct 39 ms 5760 KB Output is correct
8 Correct 45 ms 5888 KB Output is correct
9 Correct 56 ms 6144 KB Output is correct
10 Correct 90 ms 6272 KB Output is correct
11 Correct 265 ms 6520 KB Output is correct
12 Correct 156 ms 7068 KB Output is correct
13 Correct 242 ms 6712 KB Output is correct
14 Correct 399 ms 7296 KB Output is correct
15 Correct 834 ms 9136 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2292 ms 25512 KB Output isn't correct
2 Incorrect 2371 ms 22264 KB Output isn't correct
3 Incorrect 6631 ms 23464 KB Output isn't correct
4 Correct 445 ms 7288 KB Output is correct
5 Correct 717 ms 8576 KB Output is correct
6 Incorrect 914 ms 55456 KB Output isn't correct
7 Correct 3033 ms 26048 KB Output is correct
8 Runtime error 491 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Correct 7365 ms 14712 KB Output is correct
10 Runtime error 604 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Execution timed out 8050 ms 14716 KB Time limit exceeded
12 Correct 3533 ms 21612 KB Output is correct
13 Correct 4892 ms 21868 KB Output is correct
14 Incorrect 5397 ms 75652 KB Output isn't correct
15 Execution timed out 8045 ms 26184 KB Time limit exceeded
16 Execution timed out 8041 ms 31804 KB Time limit exceeded
17 Execution timed out 8031 ms 86952 KB Time limit exceeded