oj.uz

답안 #526426

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526426 2022-02-14T17:59:44 Z 1ne Regions (IOI09_regions) C++14
0 / 100
 2357 ms 131076 KB 
#include<bits/stdc++.h>
using namespace std;
 
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,r,q;cin>>n>>r>>q;
vector<int>region(n,-1),parent(n,-1);
cin>>region[0];
region[0]--;
vector<vector<int>>adj(n);
vector<int>region_count(r,0);
for (int i = 1;i<n;++i){
	adj[0].push_back(i);
	cin>>parent[i]>>region[i];
	parent[i]--;
	adj[parent[i]].push_back(i);
	region[i]--;
	region_count[region[i]]++;
}
vector<bool>visited(n,false);
vector<vector<int>>arr(r);
vector<bool>op(r,false);
op[region[0]]=true;
function<void(int , int)> dfs = [&](int cur,int par){
	//visited[cur] = true;
	for (auto x:adj[cur]){
		//if (x==par)continue;
		if (x==0){
			op[region[x]]=true;
			continue;
		}
		arr[region[par]].push_back(region[x]);
		dfs(x,par);
	}
};
for (int i = 1;i<n;++i){
	//if (!visited[i])
		dfs(i,i);
}
for (int i = 0;i<r;++i){
	sort(arr[i].begin(),arr[i].end());
}
for (int i = 0;i<q;++i){
	int x,y;cin>>x>>y;
	--x;
	--y;
	if (op[x]){
		cout<<region_count[y]<<endl;
		continue;
	}
	if (arr[x].empty()){
		cout<<0<<endl;
	}
	int ans = 0;
	int left = 0,right = arr[x].size()-1;
	while(left<=right){
		int mid = (left + right)>>1;
		if (arr[x][mid]<=y){
			left = mid + 1;
			ans = max(ans,mid);
		}
		else{
			right = mid - 1;
		}
	}
	int ans2 = INT_MAX;
	int left2 = 0,right2 = arr[x].size()-1;
	while(left2<=right2){
		int mid = (left2 + right2)>>1;
		if (arr[x][mid]>=y){
			ans2 = min(ans2,mid);
			right2 = mid - 1;
		}
		else left2 = mid + 1;
	}
	cout<<max(ans - ans2 + 1,0)<<endl;
	
}
return 0;}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 200 KB Output isn't correct
2 Incorrect 1 ms 200 KB Output isn't correct
3 Incorrect 1 ms 200 KB Output isn't correct
4 Incorrect 1 ms 200 KB Output isn't correct
5 Incorrect 9 ms 456 KB Output isn't correct
6 Incorrect 21 ms 2120 KB Output isn't correct
7 Incorrect 33 ms 840 KB Output isn't correct
8 Incorrect 41 ms 1968 KB Output isn't correct
9 Incorrect 773 ms 62040 KB Output isn't correct
10 Incorrect 141 ms 6080 KB Output isn't correct
11 Incorrect 383 ms 23532 KB Output isn't correct
12 Runtime error 532 ms 131076 KB Execution killed with signal 9
13 Incorrect 182 ms 4712 KB Output isn't correct
14 Incorrect 517 ms 25384 KB Output isn't correct
15 Runtime error 516 ms 131076 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 724 ms 131076 KB Execution killed with signal 9
2 Runtime error 701 ms 131076 KB Execution killed with signal 9
3 Runtime error 619 ms 131076 KB Execution killed with signal 9
4 Runtime error 735 ms 131076 KB Execution killed with signal 9
5 Runtime error 493 ms 131072 KB Execution killed with signal 9
6 Runtime error 764 ms 131076 KB Execution killed with signal 9
7 Runtime error 838 ms 131076 KB Execution killed with signal 9
8 Runtime error 576 ms 131076 KB Execution killed with signal 9
9 Runtime error 1797 ms 131076 KB Execution killed with signal 9
10 Runtime error 650 ms 131076 KB Execution killed with signal 9
11 Runtime error 1462 ms 131076 KB Execution killed with signal 9
12 Runtime error 2357 ms 131076 KB Execution killed with signal 9
13 Runtime error 1527 ms 131076 KB Execution killed with signal 9
14 Runtime error 2050 ms 131076 KB Execution killed with signal 9
15 Runtime error 818 ms 131076 KB Execution killed with signal 9
16 Runtime error 674 ms 131076 KB Execution killed with signal 9
17 Runtime error 595 ms 131076 KB Execution killed with signal 9