| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 769071 | ono_de206 | Highway Tolls (IOI18_highway) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
// #define int long long
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
const int mxn = 1e5 + 10;
void find_pair(int n, vector<int> u, vector<int> v, int A, int B) {
int m = u.size();
for(int i = 0; i < m; i++) {
g[u[i]].pb(v[i]);
g[v[i]].pb(u[i]);
}
long long tot = ask(vector<int>(m));
int l = 0, r = m;
while(r - l > 1) {
int mid = (r + l) / 2;
vector<int> q(m);
for(int i = 0; i <= mid; i++) {
q[i] = 1;
}
if(ask(q) == tot) l = m;
else r = m;
}
int x = u[l], y = v[l], ans1, ans2;
auto bfs = [&](int st) -> vector<int> {
vector<int> ret(n, -1);
ret[st] = 0;
queue<int> q;
q.push(st);
while(q.size()) {
int x = q.front();
q.pop();
for(int y : g[x]) {
if(ret[y] != -1) continue;
ret[y] = ret[x] + 1;
q.push(y);
}
}
return ret;
};
auto disX = bfs(x);
auto disY = bfs(y);
vector<int> edges;
for(int i = 0; i < m; i++) {
if(disX[u[i]] > disX[v[i]]) swap(u[i], v[i]);
if(disX[u[i]] < disY[u[i]] && disX[v[i]] < disY[v[i]]) edges.pb(i);
}
sort(all(edges), [&](int id1, int id2) {
return disX[v[id1]] < disX[v[id2]];
});
int l = -1, r = edges.size();
while(r - l > 1) {
int mid = (l + r) / 2;
vector<int> q(m);
for(int i = 0; i <= mid; i++) {
q[edges[i]] = 1;
}
if(ask(q) == tot) r = m;
else l = m;
}
if(l == -1) ans1 = x;
else ans1 = v[edges[l]];
edges.clear();
for(int i = 0; i < m; i++) {
if(disY[u[i]] > disY[v[i]]) swap(u[i], v[i]);
if(disY[u[i]] < disX[u[i]] && disY[v[i]] < disX[v[i]]) edges.pb(i);
}
sort(all(edges), [&](int id1, int id2) {
return disY[v[id1]] < disY[v[id2]];
});
int l = -1, r = edges.size();
while(r - l > 1) {
int mid = (l + r) / 2;
vector<int> q(m);
for(int i = 0; i <= mid; i++) {
q[edges[i]] = 1;
}
if(ask(q) == tot) r = m;
else l = m;
}
if(l == -1) ans2 = y;
else ans2 = v[edges[l]];
answer(ans1, ans2);
}