| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1055124 | Ahmed57 | 통행료 (IOI18_highway) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
#include "highway.h"
using namespace std;
#define int long long
pair<int,int> p[100001];
int dep[100001];
vector<pair<int,int>> adj[100001];
void dfs(int i,int pr,int id){
dep[i] = dep[pr]+1;
p[i] = {pr,id};
for(auto j:adj[i]){
if(j.first==pr)continue;
dfs(j.first,i,j.second);
}
}
void find_pair(int32_t N, vector<int32_t> U, vector<int32_t> V, int32_t A, int32_t B){
int m = U.size();
vector<int> as(m,0);
vector<int> as2(m,1);
int len = ask(as);
int len2 = ask(as2);
for(int i = 0;i<U.size();i++){
adj[U[i]].push_back({V[i],i});
adj[V[i]].push_back({U[i],i});
}
dfs(0,0,-1);
vector<pair<int,int>> v;
for(int i = 0;i<N;i++){
v.push_back({dep[i],i});
}
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
int l = 0 , r = v.size()-2 , ans = 0;
while(l<=r){
int mid = (l+r)/2;
vector<int> as(m,0);
for(int i = 0;i<=mid;i++){
as[p[v[i].second].second] = 1;
}
if(ask(as)!=len){
ans = mid;
r = mid-1;
}else l = mid+1;
}
int a = v[ans].second;
if(len/A==len2/B){
int x = len/A;
int b = a;
while(x--){
b = p[b].first;
}
answer(a,b);
return ;
}
l = 2 , r = dep[a] ;int ans2 = 0;
while(l<=r){
int mid = (l+r)/2;
vector<int> as(m,0);
for(int i = 0;i<N;i++){
if(dep[i]>=mid){
as[p[i].second] =1 ;
}
}
int na = ask(as);
if(na!=(dep[a]-mid+1)*B){
ans2 = mid;
l = mid+1;
}else r = mid-1;
}
vector<int> lol;
l = -1;
for(int i = 0;i<v.size();i++){
if(v[i].first==ans2&&l==-1)l = i;
if(v[i].first==ans2)r = i;
}
int ans3 = 0;
while(l<=r){
int mid = (l+r)/2;
vector<int> as(m,0);
for(int i = 0;i<=mid;i++){
as[p[v[i].second].second] = 1;
}
if(ask(as)==(dep[a]-ans2+1)*B+B){
ans3 = mid;
r = mid-1;
}else l = mid+1;
}
int b = v[ans3].second;
answer(a,b);
}