Submission #805140

#	Time	Username	Problem	Language	Result	Execution time	Memory
805140		1bin	통행료 (IOI18_highway)	C++14	100 / 100	159 ms	11296 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
ll n, m, d[NMAX], cost;
vector<pair<int, int>> adj[NMAX];
vector<int> A[2];

/*
ll ask(vector<int> w){
    cout << "query : ";
    for(int i = 0; i < m; i++) cout << w[i] << ' ';
    cout << endl;
    ll x;
    cin >> x;
    return x;
}

void answer(int s, int t){
    cout << s << ' ' << t << '\n';
    return;
}
*/

void find_pair(int n_, vector<int> U, std::vector<int> V, int a, int b) {
    n = n_; m = U.size();
    for(int i = 0; i < m; i++){
        adj[U[i]].emplace_back(V[i], i);
        adj[V[i]].emplace_back(U[i], i);
    }
    cost = ask(vector<int>(m));
    int l = 0, r = m - 1, mid;
    while(l < r){
        mid = (l + r) / 2;
        vector<int> w(m);
        fill(w.begin(), w.begin() + mid + 1, 1);
        if(ask(w) > cost) r = mid;
        else l = mid + 1;
    }

    int u[2] = {U[l], V[l]};
    memset(d, 0x3f, sizeof(d));
    d[u[0]] = d[u[1]] = 1;
    queue<pair<int, int>> q;
    q.emplace(u[0], 0); q.emplace(u[1], 1);
    while(q.size()){
        auto[x, p] = q.front(); q.pop();
        A[p].emplace_back(x);
        for(auto&[nx, e] : adj[x])
            if(d[x] + 1 < d[nx]){
                d[nx] = d[x] + 1;
                q.emplace(nx, p);
            }
    }
    int v[2];
    for(int t = 0; t < 2; t++){
        int l = 0, r = A[t].size() - 1, mid;
        while(l < r){
            mid = (l + r) / 2;
            vector<int> w(m);
            for(int i = mid + 1; i <= r; i++)
                for(auto&[j, e] : adj[A[t][i]]) w[e] = 1;
            if(ask(w) > cost) l = mid + 1;
            else r = mid;
        }
        v[t] = A[t][l];
    }
    answer(v[0], v[1]);
    return;
}

/*
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m, a, b, s, t;
    cin >> n >> m >> a >> b >> s >> t;
    vector<int> U(m), V(m);
    for(int i = 0; i < m; i++) cin >> U[i] >> V[i];
    find_pair(n, U, V, a, b);
    return 0;
}
*/

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:51:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |         auto[x, p] = q.front(); q.pop();
      |             ^
highway.cpp:53:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |         for(auto&[nx, e] : adj[x])
      |                  ^
highway.cpp:66:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |                 for(auto&[j, e] : adj[A[t][i]]) w[e] = 1;
      |                          ^

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 18 / 18
• Subtask 6: 31 / 31