oj.uz

답안 #526441

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526441 2022-02-14T18:47:29 Z 1ne Regions (IOI09_regions) C++14
13 / 100
 665 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);
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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