# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
497178 | MohamedFaresNebili | 통행료 (IOI18_highway) | C++14 | 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<bits/stdc++.h>
#include "highway.h"
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using vi = vector<int>;
#define pb push_back
#define ff first
#define ss second
#define lb lower_bound
#define all(x) (x).begin() , (x).end()
vector<ii> adj[2*100005]; ll par[2*100005], dep[2*100005];
void dfs(ll v, ll p) {
dep[v] = dep[p] + 1;
for(auto u : adj[v]) {
if(u.ff == p) continue;
par[u.ff] = u.ss; dfs(u.ff, v);
}
}
ll ask(vector<ll> w);
void answer(ll s, ll t);
void find_pair(ll N, vector<ll> U, vector<ll> V, ll A, ll B) {
ll M = U.size();
vector<ll> w(M, 0); ll k = ask(w);
k /= A;
for(ll l = 0; l < M; l++) {
ll u = U[l], v = V[l];
adj[u].pb({v, l}); adj[v].pb({u, l});
}
dep[0] = -1; dfs(0, 0);
vector<ll> ve;
for(ll l = 0; l < N; l++) {
if(dep[l] != k) continue;
ve.push_back(l);
}
for(auto u : ve) {
ll id = par[u];
w[id] = 1; ll curr = ask(w); w[id] = 0;
if(curr > k) { answer(0, u); return; }
}
}