| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 526309 |
2022-02-14T08:58:28 Z |
1ne |
Regions (IOI09_regions) |
C++14 |
|
1681 ms |
33616 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[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());
}
for (int i = 0;i<q;++i){
int x,y;cin>>x>>y;
--x;
--y;
if (op[x]){
cout<<region_count[y]<<endl;
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;
}
cout<<ans - ans2 + 1<<endl;
}
return 0;}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
200 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
200 KB |
Output isn't correct |
| 4 |
Incorrect |
5 ms |
200 KB |
Output isn't correct |
| 5 |
Incorrect |
6 ms |
328 KB |
Output isn't correct |
| 6 |
Incorrect |
20 ms |
328 KB |
Output isn't correct |
| 7 |
Incorrect |
19 ms |
400 KB |
Output isn't correct |
| 8 |
Incorrect |
32 ms |
456 KB |
Output isn't correct |
| 9 |
Incorrect |
48 ms |
1096 KB |
Output isn't correct |
| 10 |
Incorrect |
59 ms |
968 KB |
Output isn't correct |
| 11 |
Incorrect |
68 ms |
1480 KB |
Output isn't correct |
| 12 |
Incorrect |
96 ms |
2216 KB |
Output isn't correct |
| 13 |
Incorrect |
131 ms |
1752 KB |
Output isn't correct |
| 14 |
Incorrect |
152 ms |
2376 KB |
Output isn't correct |
| 15 |
Incorrect |
140 ms |
6980 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
617 ms |
6976 KB |
Output isn't correct |
| 2 |
Incorrect |
756 ms |
5296 KB |
Output isn't correct |
| 3 |
Incorrect |
970 ms |
10048 KB |
Output isn't correct |
| 4 |
Incorrect |
167 ms |
2632 KB |
Output isn't correct |
| 5 |
Incorrect |
128 ms |
5572 KB |
Output isn't correct |
| 6 |
Incorrect |
482 ms |
4576 KB |
Output isn't correct |
| 7 |
Incorrect |
670 ms |
5836 KB |
Output isn't correct |
| 8 |
Incorrect |
751 ms |
14408 KB |
Output isn't correct |
| 9 |
Incorrect |
1134 ms |
13364 KB |
Output isn't correct |
| 10 |
Incorrect |
1144 ms |
22212 KB |
Output isn't correct |
| 11 |
Incorrect |
1681 ms |
13536 KB |
Output isn't correct |
| 12 |
Incorrect |
574 ms |
14828 KB |
Output isn't correct |
| 13 |
Incorrect |
866 ms |
15728 KB |
Output isn't correct |
| 14 |
Incorrect |
1248 ms |
15200 KB |
Output isn't correct |
| 15 |
Incorrect |
1454 ms |
22532 KB |
Output isn't correct |
| 16 |
Incorrect |
1625 ms |
33616 KB |
Output isn't correct |
| 17 |
Incorrect |
1679 ms |
31076 KB |
Output isn't correct |
