Submission #526447

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526447	2022-02-14T19:00:53 Z	1ne	Regions (IOI09_regions)	C++14	0 / 100	57 ms	14584 KB

regions

#include<bits/stdc++.h>
using namespace std;
 
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int64_t n,r,q;cin>>n>>r>>q;
vector<int64_t>region(n,-1),parent(n,-1);
cin>>region[0];
region[0]--;
vector<vector<int64_t>>adj(n);
for (int64_t i = 1;i<n;++i){
	cin>>parent[i]>>region[i];
	parent[i]--;
	adj[parent[i]].push_back(i);
	region[i]--;
}
set<pair<int,int>>need;
vector<pair<int,int>>query;
vector<bool>visited(n,false);
vector<int64_t>region_count(r,0);
for (int64_t i = 0;i<q;++i){
	int64_t x,y;cin>>x>>y;
	--x;
	--y;
	need.insert({x,y});
	query.push_back({x,y});
}
map<pair<int64_t,int64_t>,int64_t>brr;
function<void(int64_t)> dfs = [&](int64_t cur){
	if (visited[cur]){
		return;
	}
	visited[cur]=true;
	for (int j = 0;j<r;++j){
		if (j!=region[cur]&&region_count[j]>0&&need.find({j,region[cur]})!=need.end())
			brr[{j,region[cur]}]+=region_count[j];
	}
	region_count[region[cur]]++;
	for (auto x:adj[cur]){
		if (!visited[x])
			dfs(x);
	}
	region_count[region[cur]]--;
};

for (int64_t i = 0;i<n;++i){
	if (!visited[i]){
		dfs(i);
	}
}
for (auto x:query){
	cout<<brr[x]<<endl;
}

return 0;}

Subtask #1

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1 ms	200 KB	Time limit exceeded (wall clock)
2	Execution timed out	1 ms	200 KB	Time limit exceeded (wall clock)
3	Execution timed out	0 ms	200 KB	Time limit exceeded (wall clock)
4	Execution timed out	1 ms	200 KB	Time limit exceeded (wall clock)
5	Execution timed out	0 ms	328 KB	Time limit exceeded (wall clock)
6	Execution timed out	1 ms	328 KB	Time limit exceeded (wall clock)
7	Execution timed out	1 ms	328 KB	Time limit exceeded (wall clock)
8	Execution timed out	1 ms	328 KB	Time limit exceeded (wall clock)
9	Execution timed out	1 ms	584 KB	Time limit exceeded (wall clock)
10	Execution timed out	3 ms	968 KB	Time limit exceeded (wall clock)
11	Execution timed out	3 ms	1352 KB	Time limit exceeded (wall clock)
12	Execution timed out	4 ms	1736 KB	Time limit exceeded (wall clock)
13	Execution timed out	5 ms	1608 KB	Time limit exceeded (wall clock)
14	Execution timed out	6 ms	2268 KB	Time limit exceeded (wall clock)
15	Execution timed out	11 ms	3144 KB	Time limit exceeded (wall clock)

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	14 ms	5448 KB	Time limit exceeded (wall clock)
2	Execution timed out	16 ms	5064 KB	Time limit exceeded (wall clock)
3	Execution timed out	17 ms	6600 KB	Time limit exceeded (wall clock)
4	Execution timed out	6 ms	2248 KB	Time limit exceeded (wall clock)
5	Execution timed out	7 ms	2888 KB	Time limit exceeded (wall clock)
6	Execution timed out	11 ms	3656 KB	Time limit exceeded (wall clock)
7	Execution timed out	15 ms	4928 KB	Time limit exceeded (wall clock)
8	Execution timed out	20 ms	7332 KB	Time limit exceeded (wall clock)
9	Execution timed out	31 ms	10564 KB	Time limit exceeded (wall clock)
10	Execution timed out	37 ms	12416 KB	Time limit exceeded (wall clock)
11	Execution timed out	45 ms	12352 KB	Time limit exceeded (wall clock)
12	Execution timed out	57 ms	13632 KB	Time limit exceeded (wall clock)
13	Execution timed out	44 ms	13252 KB	Time limit exceeded (wall clock)
14	Execution timed out	42 ms	13504 KB	Time limit exceeded (wall clock)
15	Execution timed out	44 ms	14584 KB	Time limit exceeded (wall clock)
16	Execution timed out	41 ms	14492 KB	Time limit exceeded (wall clock)
17	Execution timed out	41 ms	14528 KB	Time limit exceeded (wall clock)