Submission #526443

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526443	2022-02-14T18:52:24 Z	1ne	Regions (IOI09_regions)	C++14	30 / 100	3249 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);
vector<map<int64_t,int64_t>>brr(r);
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;
	if (brr[x].find(y)!=brr[x].end()){
		cout<<brr[x][y]<<endl;
	}
	else cout<<0<<endl;
	
}
return 0;}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	328 KB	Output is correct
5	Correct	9 ms	456 KB	Output is correct
6	Correct	39 ms	3544 KB	Output is correct
7	Correct	36 ms	1352 KB	Output is correct
8	Correct	52 ms	2376 KB	Output is correct
9	Correct	222 ms	6732 KB	Output is correct
10	Correct	217 ms	8768 KB	Output is correct
11	Correct	347 ms	5952 KB	Output is correct
12	Correct	1579 ms	14820 KB	Output is correct
13	Correct	185 ms	6384 KB	Output is correct
14	Correct	441 ms	4960 KB	Output is correct
15	Correct	985 ms	10500 KB	Output is correct

Subtask #2

15.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1741 ms	9396 KB	Output is correct
2	Correct	1989 ms	8424 KB	Output is correct
3	Correct	3249 ms	14156 KB	Output is correct
4	Runtime error	2938 ms	131076 KB	Execution killed with signal 9
5	Runtime error	3160 ms	131076 KB	Execution killed with signal 9
6	Runtime error	2456 ms	131076 KB	Execution killed with signal 9
7	Runtime error	1454 ms	131076 KB	Execution killed with signal 9
8	Runtime error	3058 ms	131076 KB	Execution killed with signal 9
9	Runtime error	2044 ms	131076 KB	Execution killed with signal 9
10	Runtime error	3218 ms	131076 KB	Execution killed with signal 9
11	Runtime error	3202 ms	131076 KB	Execution killed with signal 9
12	Runtime error	2841 ms	131076 KB	Execution killed with signal 9
13	Runtime error	2334 ms	131076 KB	Execution killed with signal 9
14	Runtime error	2661 ms	131076 KB	Execution killed with signal 9
15	Runtime error	2131 ms	131076 KB	Execution killed with signal 9
16	Runtime error	2328 ms	131076 KB	Execution killed with signal 9
17	Runtime error	1885 ms	131076 KB	Execution killed with signal 9