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 ll = long long;
using namespace std;
#define pb push_back
#define sz(x) (int)x.size()
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
int M = U.size();
vector<int> tmp(M, 0);
vector<vector<pair<int,int>>> adj(N+1);
for(int i=0; i<M; ++i){
adj[U[i]].pb({V[i], i});
adj[V[i]].pb({U[i], i});
}
ll W = ask(tmp);
int aristas = W / A;
vector<int> pa(N+1, -1);
auto bfs = [&](int at) -> vector<int> {
vector<int> res;
vector<int> dis(N+1, N+10);
queue<int> q;
q.push(at);
dis[at] = 0;
while(sz(q)){
int cur = q.front();
q.pop();
if(dis[cur] == aristas){
res.pb(cur);
}
for(auto [u, id] : adj[cur]){
if(dis[cur] + 1 < dis[u]){
dis[u] = dis[cur] + 1;
q.push(u);
pa[u] = id;
}
}
}
return res;
};
vector<int> cands = bfs(0);
int ans = 0;
for(int x : cands){
int ante = pa[x];
tmp[ante] = 1;
ll w = ask(tmp);
if(w != W){
ans = x;
break;
}
tmp[ante] = 0;
}
answer(0, ans);
}
Compilation message (stderr)
highway.cpp: In lambda function:
highway.cpp:39:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
39 | for(auto [u, id] : adj[cur]){
| ^
# | 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... |