Submission #526441

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526441	2022-02-14T18:47:29 Z	1ne	Regions (IOI09_regions)	C++14	13 / 100	665 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<vector<pair<int64_t,int64_t>>>arr(r);
vector<bool>visited(n,false);
vector<int64_t>region_count(r,0);
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)
			arr[j].push_back({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;
	if (arr[x].empty()){
		cout<<0<<endl;
		continue;
	}
	int64_t ans = -1;
	int64_t left = 0,right = arr[x].size()-1;
	while(left<=right){
		int64_t mid = (left + right)>>1;
		if (arr[x][mid].first<=y){
			left = mid + 1;
		}
		else{
			right = mid - 1;
		}
		if (arr[x][mid].first==y){
			ans = max(ans,mid);
		}
	}
	int64_t ans2 = INT_MAX;
	int64_t left2 = 0,right2 = arr[x].size()-1;
	while(left2<=right2){
		int64_t mid = (left2 + right2)>>1;
		if (arr[x][mid].first>=y){
			right2 = mid - 1;
		}
		else left2 = mid + 1;
		if (arr[x][mid].first==y){
			ans2 = min(ans2,mid);
		}
	}
	int64_t ans3 = 0;
	if (ans>=0){
		ans3+=arr[x][ans].second;
	}
	if (ans2>0&&ans2<INT_MAX){
		ans3-=arr[x][ans2-1].second;
	}
	cout<<max(ans3,(int64_t)0)<<endl;
	
}
return 0;}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:45: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]
   45 |  for (int j = 1;j<arr[i].size();++j){
      |                 ~^~~~~~~~~~~~~~

Subtask #1

13.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	5 ms	328 KB	Output is correct
5	Correct	8 ms	712 KB	Output is correct
6	Correct	28 ms	3528 KB	Output is correct
7	Correct	16 ms	2180 KB	Output is correct
8	Correct	42 ms	4232 KB	Output is correct
9	Correct	192 ms	32236 KB	Output is correct
10	Correct	142 ms	19272 KB	Output is correct
11	Correct	328 ms	46308 KB	Output is correct
12	Runtime error	167 ms	131076 KB	Execution killed with signal 9
13	Correct	116 ms	13728 KB	Output is correct
14	Correct	411 ms	57772 KB	Output is correct
15	Runtime error	164 ms	131076 KB	Execution killed with signal 9

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	221 ms	131076 KB	Execution killed with signal 9
2	Runtime error	197 ms	131076 KB	Execution killed with signal 9
3	Runtime error	169 ms	131076 KB	Execution killed with signal 9
4	Runtime error	255 ms	131076 KB	Execution killed with signal 9
5	Runtime error	189 ms	131076 KB	Execution killed with signal 9
6	Runtime error	258 ms	131076 KB	Execution killed with signal 9
7	Runtime error	309 ms	131076 KB	Execution killed with signal 9
8	Runtime error	264 ms	131076 KB	Execution killed with signal 9
9	Runtime error	311 ms	131076 KB	Execution killed with signal 9
10	Runtime error	396 ms	131076 KB	Execution killed with signal 9
11	Runtime error	665 ms	131076 KB	Execution killed with signal 9
12	Runtime error	455 ms	131076 KB	Execution killed with signal 9
13	Runtime error	439 ms	131076 KB	Execution killed with signal 9
14	Runtime error	518 ms	131076 KB	Execution killed with signal 9
15	Runtime error	387 ms	131076 KB	Execution killed with signal 9
16	Runtime error	414 ms	131076 KB	Execution killed with signal 9
17	Runtime error	328 ms	131076 KB	Execution killed with signal 9