oj.uz

Submission #116559

# Submission time Handle Problem Language Result Execution time Memory
116559 2019-06-13T00:02:40 Z kig9981 Regions (IOI09_regions) C++17
30 / 100
 8000 ms 52092 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[200000], sum2[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)
{
	sum[c]+=RV[c]==O[idx];
	sum2[c]=RV[c]==O[idx];
	for(auto n: adj[c]) {
		sum[n]=sum[c];
		dfs2(n,idx);
		sum2[c]+=sum2[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);
		sum[0]=0;
		dfs2(0,O.size()-1);
		for(int j=0;j<N;j++) {
			ans[i][RV[j]].first+=sum[j];
			ans[i][RV[j]].second+=sum2[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(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;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5760 KB Output is correct
2 Correct 6 ms 5760 KB Output is correct
3 Correct 8 ms 5632 KB Output is correct
4 Correct 8 ms 5760 KB Output is correct
5 Correct 13 ms 5636 KB Output is correct
6 Correct 19 ms 5632 KB Output is correct
7 Correct 26 ms 5632 KB Output is correct
8 Correct 47 ms 5760 KB Output is correct
9 Correct 33 ms 6016 KB Output is correct
10 Correct 61 ms 6064 KB Output is correct
11 Correct 142 ms 6400 KB Output is correct
12 Correct 221 ms 6784 KB Output is correct
13 Correct 193 ms 6656 KB Output is correct
14 Correct 417 ms 7168 KB Output is correct
15 Correct 468 ms 8960 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1658 ms 10872 KB Output isn't correct
2 Incorrect 1724 ms 9976 KB Output isn't correct
3 Incorrect 3287 ms 12792 KB Output isn't correct
4 Correct 362 ms 7080 KB Output is correct
5 Correct 313 ms 8440 KB Output is correct
6 Runtime error 40 ms 17144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 65 ms 19192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 73 ms 31096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Correct 4986 ms 14120 KB Output is correct
10 Runtime error 104 ms 39692 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Execution timed out 8064 ms 14052 KB Time limit exceeded
12 Runtime error 172 ms 32916 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 147 ms 33276 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 234 ms 34020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 147 ms 41000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 131 ms 52092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 148 ms 51060 KB Execution killed with signal 11 (could be triggered by violating memory limits)