oj.uz

Submission #526442

# Submission time Handle Problem Language Result Execution time Memory
526442 2022-02-14T18:50:26 Z 1ne Regions (IOI09_regions) C++14
30 / 100
 3742 ms 131076 KB 
#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<vector<pair<int64_t,int64_t>>>arr(r);
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<r;++i){
	sort(arr[i].begin(),arr[i].end());
	for (int j = 1;j<arr[i].size();++j){
		arr[i][j].second+=arr[i][j-1].second;
	}
}
for (int64_t i = 0;i<q;++i){
	int64_t x,y;cin>>x>>y;
	--x;
	--y;
	cout<<brr[x][y]<<endl;
}
return 0;}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (int j = 1;j<arr[i].size();++j){
      |                 ~^~~~~~~~~~~~~~

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 2 ms 200 KB Output is correct
4 Correct 4 ms 328 KB Output is correct
5 Correct 8 ms 456 KB Output is correct
6 Correct 38 ms 3664 KB Output is correct
7 Correct 28 ms 1420 KB Output is correct
8 Correct 44 ms 2480 KB Output is correct
9 Correct 193 ms 6752 KB Output is correct
10 Correct 219 ms 8908 KB Output is correct
11 Correct 335 ms 6076 KB Output is correct
12 Correct 1513 ms 14828 KB Output is correct
13 Correct 200 ms 6824 KB Output is correct
14 Correct 551 ms 4708 KB Output is correct
15 Correct 1008 ms 10472 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1682 ms 9408 KB Output is correct
2 Correct 1786 ms 8420 KB Output is correct
3 Correct 3108 ms 14216 KB Output is correct
4 Runtime error 3341 ms 131076 KB Execution killed with signal 9
5 Runtime error 3742 ms 131076 KB Execution killed with signal 9
6 Runtime error 2270 ms 131076 KB Execution killed with signal 9
7 Runtime error 1503 ms 131076 KB Execution killed with signal 9
8 Runtime error 3027 ms 131076 KB Execution killed with signal 9
9 Runtime error 2084 ms 131076 KB Execution killed with signal 9
10 Runtime error 3176 ms 131076 KB Execution killed with signal 9
11 Runtime error 3120 ms 131076 KB Execution killed with signal 9
12 Runtime error 2890 ms 131076 KB Execution killed with signal 9
13 Runtime error 2401 ms 131076 KB Execution killed with signal 9
14 Runtime error 2659 ms 131076 KB Execution killed with signal 9
15 Runtime error 2050 ms 131076 KB Execution killed with signal 9
16 Runtime error 2152 ms 131076 KB Execution killed with signal 9
17 Runtime error 1955 ms 131076 KB Execution killed with signal 9