Submission #526450

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526450	2022-02-14T19:14:09 Z	1ne	Regions (IOI09_regions)	C++14	30 / 100	3883 ms	131076 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]--;
}
vector<bool>visited(n,false);
vector<int64_t>region_count(r,0);
map<pair<int64_t,int64_t>,int64_t>brr;
function<void(int64_t)> dfs = [&](int64_t cur){
	if (visited[cur]){
		return;
	}
	visited[cur]=true;
	
	region_count[region[cur]]++;
	for (auto x:adj[cur]){
		if (!visited[x])
			dfs(x);
	}
	for (int j = 0;j<r;++j){
		if (j!=region[cur]&&region_count[j]>0)
			brr[{j,region[cur]}]+=region_count[j];
	}
	region_count[region[cur]]--;
};

for (int64_t i = 0;i<n;++i){
	if (!visited[i]){
		dfs(i);
	}
}
for (int64_t i = 0;i<q;++i){
	int64_t x,y;cin>>x>>y;
	--x;
	--y;
	cout<<brr[{x,y}]<<endl;
	
}
return 0;}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	200 KB	Output is correct
2	Correct	1 ms	200 KB	Output is correct
3	Correct	3 ms	200 KB	Output is correct
4	Correct	5 ms	336 KB	Output is correct
5	Correct	8 ms	456 KB	Output is correct
6	Correct	34 ms	3656 KB	Output is correct
7	Correct	38 ms	1372 KB	Output is correct
8	Correct	68 ms	2632 KB	Output is correct
9	Correct	145 ms	6748 KB	Output is correct
10	Correct	251 ms	9004 KB	Output is correct
11	Correct	535 ms	5968 KB	Output is correct
12	Correct	1016 ms	14912 KB	Output is correct
13	Correct	244 ms	6712 KB	Output is correct
14	Correct	670 ms	4848 KB	Output is correct
15	Correct	792 ms	11112 KB	Output is correct

Subtask #2

15.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1729 ms	9636 KB	Output is correct
2	Correct	2656 ms	8668 KB	Output is correct
3	Correct	2336 ms	14736 KB	Output is correct
4	Runtime error	2695 ms	131076 KB	Execution killed with signal 9
5	Runtime error	1084 ms	131076 KB	Execution killed with signal 9
6	Runtime error	2392 ms	131076 KB	Execution killed with signal 9
7	Runtime error	1386 ms	131076 KB	Execution killed with signal 9
8	Runtime error	925 ms	131076 KB	Execution killed with signal 9
9	Runtime error	1472 ms	131076 KB	Execution killed with signal 9
10	Runtime error	1100 ms	131076 KB	Execution killed with signal 9
11	Runtime error	3883 ms	131072 KB	Execution killed with signal 9
12	Runtime error	2584 ms	131076 KB	Execution killed with signal 9
13	Runtime error	2411 ms	131076 KB	Execution killed with signal 9
14	Runtime error	2828 ms	131076 KB	Execution killed with signal 9
15	Runtime error	510 ms	131076 KB	Execution killed with signal 9
16	Runtime error	343 ms	131076 KB	Execution killed with signal 9
17	Runtime error	1278 ms	131076 KB	Execution killed with signal 9