oj.uz

답안 #526306

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526306 2022-02-14T08:51:45 Z 1ne Regions (IOI09_regions) C++14
0 / 100
 95 ms 33552 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);
function<void(int , int)> dfs = [&](int cur,int par){
	visited[cur] = true;
	for (auto x:adj[cur]){
		if (x==par)continue;
		arr[region[cur]].push_back(region[x]);
		dfs(x,cur);
	}
};
for (int i = 1;i<n;++i){
	if (!visited[i])
		dfs(i,-1);
}
for (int i = 0;i<r;++i){
	sort(arr[i].begin(),arr[i].end());
}
vector<int>output;
for (int i = 0;i<q;++i){
	int x,y;cin>>x>>y;
	--x;
	--y;
	if (x==region[0]){
		output.push_back(region_count[y]);
		continue;
	}
	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;
	}
	output.push_back(ans-ans2+1);
}
for (auto x:output){
	cout<<x<<endl;
}
return 0;}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1 ms 200 KB Time limit exceeded (wall clock)
2 Execution timed out 1 ms 200 KB Time limit exceeded (wall clock)
3 Execution timed out 0 ms 200 KB Time limit exceeded (wall clock)
4 Execution timed out 1 ms 200 KB Time limit exceeded (wall clock)
5 Execution timed out 1 ms 328 KB Time limit exceeded (wall clock)
6 Execution timed out 1 ms 328 KB Time limit exceeded (wall clock)
7 Execution timed out 1 ms 328 KB Time limit exceeded (wall clock)
8 Execution timed out 1 ms 456 KB Time limit exceeded (wall clock)
9 Execution timed out 2 ms 1096 KB Time limit exceeded (wall clock)
10 Execution timed out 3 ms 968 KB Time limit exceeded (wall clock)
11 Execution timed out 4 ms 1480 KB Time limit exceeded (wall clock)
12 Execution timed out 5 ms 2120 KB Time limit exceeded (wall clock)
13 Execution timed out 7 ms 1736 KB Time limit exceeded (wall clock)
14 Execution timed out 11 ms 2376 KB Time limit exceeded (wall clock)
15 Execution timed out 12 ms 7056 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 23 ms 6992 KB Time limit exceeded (wall clock)
2 Execution timed out 22 ms 5320 KB Time limit exceeded (wall clock)
3 Execution timed out 25 ms 10032 KB Time limit exceeded (wall clock)
4 Execution timed out 9 ms 2572 KB Time limit exceeded (wall clock)
5 Execution timed out 11 ms 5444 KB Time limit exceeded (wall clock)
6 Execution timed out 15 ms 4552 KB Time limit exceeded (wall clock)
7 Execution timed out 22 ms 5832 KB Time limit exceeded (wall clock)
8 Execution timed out 30 ms 14324 KB Time limit exceeded (wall clock)
9 Execution timed out 49 ms 13256 KB Time limit exceeded (wall clock)
10 Execution timed out 53 ms 22036 KB Time limit exceeded (wall clock)
11 Execution timed out 65 ms 13492 KB Time limit exceeded (wall clock)
12 Execution timed out 69 ms 14860 KB Time limit exceeded (wall clock)
13 Execution timed out 62 ms 15800 KB Time limit exceeded (wall clock)
14 Execution timed out 79 ms 15200 KB Time limit exceeded (wall clock)
15 Execution timed out 62 ms 22452 KB Time limit exceeded (wall clock)
16 Execution timed out 95 ms 33552 KB Time limit exceeded (wall clock)
17 Execution timed out 86 ms 31104 KB Time limit exceeded (wall clock)