Submission #526445

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526445	2022-02-14T18:57:28 Z	1ne	Regions (IOI09_regions)	C++14	30 / 100	4748 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;
	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 (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 (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	2 ms	200 KB	Output is correct
4	Correct	5 ms	328 KB	Output is correct
5	Correct	9 ms	456 KB	Output is correct
6	Correct	36 ms	3672 KB	Output is correct
7	Correct	35 ms	1376 KB	Output is correct
8	Correct	64 ms	2368 KB	Output is correct
9	Correct	306 ms	6928 KB	Output is correct
10	Correct	315 ms	8884 KB	Output is correct
11	Correct	581 ms	5868 KB	Output is correct
12	Correct	2312 ms	14904 KB	Output is correct
13	Correct	296 ms	6648 KB	Output is correct
14	Correct	660 ms	4952 KB	Output is correct
15	Correct	1668 ms	11188 KB	Output is correct

Subtask #2

15.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2584 ms	9620 KB	Output is correct
2	Correct	2795 ms	8392 KB	Output is correct
3	Correct	4748 ms	14704 KB	Output is correct
4	Runtime error	4488 ms	131076 KB	Execution killed with signal 9
5	Runtime error	4547 ms	131076 KB	Execution killed with signal 9
6	Runtime error	3010 ms	131076 KB	Execution killed with signal 9
7	Runtime error	1886 ms	131076 KB	Execution killed with signal 9
8	Runtime error	3898 ms	131076 KB	Execution killed with signal 9
9	Runtime error	2425 ms	131076 KB	Execution killed with signal 9
10	Runtime error	3772 ms	131076 KB	Execution killed with signal 9
11	Runtime error	4191 ms	131076 KB	Execution killed with signal 9
12	Runtime error	3372 ms	131076 KB	Execution killed with signal 9
13	Runtime error	3221 ms	131076 KB	Execution killed with signal 9
14	Runtime error	3263 ms	131076 KB	Execution killed with signal 9
15	Runtime error	2428 ms	131076 KB	Execution killed with signal 9
16	Runtime error	2611 ms	131076 KB	Execution killed with signal 9
17	Runtime error	2728 ms	131076 KB	Execution killed with signal 9