Submission #1073808

#TimeUsernameProblemLanguageResultExecution timeMemory
1073808shezittHighway Tolls (IOI18_highway)C++14
12 / 100
77 ms8528 KiB
#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; int low = 0, high = sz(cands)-1; while(low <= high){ int mid = (low + high) / 2; for(int i=0; i<=mid; ++i){ tmp[pa[cands[i]]] = 1; } ll w = ask(tmp); if(w != W){ ans = cands[mid]; high = mid-1; } else { low = mid+1; } for(int i=0; i<=mid; ++i){ tmp[pa[cands[i]]] = 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...