| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 301656 | dsjong | 통행료 (IOI18_highway) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "highway.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
int A, B, N, M;
long long len;
map<pair<int, int>, int>mp;
vector<int>adj[100005];
bool vis[100005];
int par[100005];
vector<pair<int, int>>bord;
void bfs(int src){
queue<int>q;
vis[src]=true;
q.push(src);
par[src]=-1;
while(!q.empty()){
int x=q.front();
q.pop();
for(int y:adj[x]){
if(vis[y]) continue;
vis[y]=true;
q.push(y);
par[y]=x;
bord.push_back({mp[{x, y}], y});
}
}
}
int tin[100005], tout[100005];
int cnt=0;
vector<pair<int, int>>vin, vout;
void dfs(int x, int p){
tin[x]=cnt++;
for(int y:adj[x]){
if(y==p) continue;
dfs(y, x);
vin.push_back({tin[y], y});
vout.push_back({tout[y], y});
}
tout[x]=cnt++;
}
vector<int>query, askv;
bool hasB(){
for(int i=0;i<M;i++) askv[i]=0;
for(int x:query) askv[x]=1;
query.clear();
return ask(askv) > A*len;
}
void find_pair(int _N, std::vector<int> &U, std::vector<int> &V, int _A, int _B) {
A=_A, B=_B, N=_N, M=U.size();
askv.resize(M);
for(int i=0;i<M;i++) askv[i]=0;
len=ask(askv)/A;
for(int i=0;i<M;i++){
adj[U[i]].push_back(V[i]);
adj[V[i]].push_back(U[i]);
mp[{U[i], V[i]}]=i;
mp[{V[i], U[i]}]=i;
}
bfs(0);
int L=0, R=M-1;
while(L<R){
int M=(L+R)/2;
for(int i=0;i<=M;i++){
query.push_back(bord[i].first);
}
if(hasB()) R=M;
else L=M+1;
}
int rt=par[bord[L].second];
dfs(rt, par[rt]);
sort(vin.begin(), vin.end());
sort(vout.begin(), vout.end());
reverse(vin.begin(), vin.end());
int pt1, pt2;
//find largest in
L=0, R=(int) vin.size()-1;
while(L<R){
int M=(L+R)/2;
for(int i=0;i<=M;i++){
int cur=vin[i].S;
query.push_back(mp[{cur, par[cur]}]);
}
if(hasB()) R=M;
else L=M+1;
}
pt1=vin[L].S;
L=0, R=(int) vin.size()-1;
while(L<R){
int M=(L+R)/2;
for(int i=0;i<=M;i++){
int cur=vout[i].S;
query.push_back(mp[{cur, par[cur]}]);
}
if(hasB()) R=M;
else L=M+1;
}
pt2=vout[L].S;
if(pt1==pt2) answer(pt1, rt);
else answer(pt1, pt2);
}