| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 295395 | SeDunion | 통행료 (IOI18_highway) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 2e5;
vector<pair<int,int>> g[MAXN];
vector<int> h[2];
ll dist;
// map<int,int> id[MAXN];
int find(vector<int>v) {
int l = 0, r = v.size()-1;
while (l <= r) {
int m = (l + r) >> 1;
for (int i = 0 ; i < M ; ++ i) {
W[i] = 0;
}
for (int i = m ; i < v.size() ; ++ i) {
for (auto [to,qaz] : g[v[i]]) {
W[qaz] = 1;
// W[id[V[i]][to]] = 1;
}
}
if (ask(W)!=dist)l=m+1;
else r=m-1;
}
return v[l-1];
}
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]].push_back ({V[i], i});
g[V[i]].push_back ({U[i], i});
// id[U[i]][V[i]]=id[V[i]][U[i]]=i;
}
W = vector<int>(M,0);
dist = ask(W);
int l = 0, r = M - 1;
while (l <= r) {
int m = (l + r) >> 1;
for (int i = 0 ; i < M ; ++ i) {
W[i] = i <= m;
}
if (ask(W) == dist) {
l = m + 1;
} else {
r = m - 1;
}
}
int u = U[l], v = V[l];
// cout<<u<<" <-> "<<v<<'\n';
queue<pair<int,int>>q;
vector<int>d(N,MAXN);
q.push({u,0});
q.push({v,1});
d[u]=d[v]=0;
while(q.size()) {
int v, t;
tie (v, t) = q.front(); q.pop();
h[t].push_back (v);
for (auto [to, i] : g[v]) if (d[to] > d[v] + 1) {
d[to] = d[v] + 1;
q.push({to,t});
}
}
// cout<<find(h[0])<<" >-< " << find(h[1]) << "\n";
answer (find(h[0]),find(h[1]));
}