# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
292081 | zoooma13 | Highway Tolls (IOI18_highway) | C++14 | 216 ms | 13904 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;
vector<vector <pair<int ,int>>> adj;
vector <pair<int ,int>> ver;
void dfs(int u ,int p=-1 ,int f=-1){
for(auto&e : adj[u]) if(e.first != p)
dfs(e.first ,u ,e.second);
ver.push_back({u ,f});
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
assert(U.size() == N-1);
adj.resize(N);
for(int i=0; i<N-1; i++){
adj[U[i]].push_back({V[i] ,i});
adj[V[i]].push_back({U[i] ,i});
}
int S ,T;
long long emp = ask(vector<int>(N-1 ,0));
ver.clear() ,dfs(0) ,ver.pop_back();
int st = 0 ,en = N-1 ,mid;
while(st <= en){
mid = (st+en)>>1;
vector <int> t(N-1 ,0);
for(int i=st; i<=mid; i++)
t[ ver[i].second ] = 1;
if(ask(t) != emp)
en = mid-1;
else
st = mid+1;
}
S = ver[st].first;
ver.clear() ,dfs(S) ,ver.pop_back();
st = 0 ,en = N-1 ,mid;
while(st <= en){
mid = (st+en)>>1;
vector <int> t(N-1 ,0);
for(int i=st; i<=mid; i++)
t[ ver[i].second ] = 1;
if(ask(t) != emp)
en = mid-1;
else
st = mid+1;
}
T = ver[st].first;
answer(S ,T);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |