제출 #497224

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
497224		dxz05	통행료 (IOI18_highway)	C++14	0 / 100	16 ms	3388 KiB

highway

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

using namespace std;

typedef long long ll;

#define all(x) (x).begin(), (x).end()

const int MAXN = 1e5 + 3e2;

vector<pair<int, int>> g[MAXN];

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    int M = U.size();

    for (int i = 0; i < M; i++){
        g[U[i]].emplace_back(V[i], i);
        g[V[i]].emplace_back(U[i], i);
    }

    vector<int> w(M, 0);

    ll onlyA = ask(w);

    int ind = 0;

    int l = 0, r = M - 1;
    while (l <= r){
        int mid = (l + r) >> 1;
        fill(all(w), 0);
        for (int i = 0; i <= mid; i++) w[i] = 1;
        ll res = ask(w);
        if (res != onlyA){
            ind = mid;
            r = mid - 1;
        } else l = mid + 1;
    }

    int u = U[ind], v = V[ind];

    /*for (int i = 0; i < g[U[ind]].size(); i++){
        if (g[U[ind]][i].first == V[ind]) g[U[ind]].erase(g[U[ind]].begin() + i);
    }
    for (int i = 0; i < g[V[ind]].size(); i++){
        if (g[V[ind]][i].first == U[ind]) g[V[ind]].erase(g[V[ind]].begin() + i);
    }*/

    queue<int> q;
    vector<bool> used(N, false);
    vector<int> p(N, 0);
    used[u] = true;
    q.push(u);

    vector<int> edges;
    while (!q.empty()){
        int x = q.front(); q.pop();
        for (auto e : g[x]){
            int y = e.first, i = e.second;
            if (!used[y]){
                used[y] = true;
                q.push(y);
                p[y] = i;
                edges.push_back(i);
            }
        }
    }

    int S = -1, T = -1;

    l = 0, r = edges.size() - 1;

    while (l <= r){
        int mid = (l + r) >> 1;
        fill(all(w), 1);
        for (int i = 0; i <= mid; i++) w[edges[i]] = 0;
        ll res = ask(w);
        if (res == onlyA){
            int i = edges[mid];
            if (p[U[i]] == i) S = U[i]; else
                S = V[i];
            r = mid - 1;
        } else l = mid + 1;
    }

    fill(all(used), false);
    fill(all(p), 0);
    used[v] = true;
    q.push(v);

    edges.clear();
    while (!q.empty()){
        int x = q.front(); q.pop();
        for (auto e : g[x]){
            int y = e.first, i = e.second;
            if (!used[y]){
                used[y] = true;
                q.push(y);
                p[y] = i;
                edges.push_back(i);
            }
        }
    }

    l = 0, r = edges.size() - 1;

    while (l <= r){
        int mid = (l + r) >> 1;
        fill(all(w), 1);
        for (int i = 0; i <= mid; i++) w[edges[i]] = 0;
        ll res = ask(w);
        if (res == onlyA){
            int i = edges[mid];
            if (p[U[i]] == i) T = U[i]; else
                T = V[i];
            r = mid - 1;
        } else l = mid + 1;
    }

    cerr << S << ' ' << T << endl;

    answer(S, T);
}

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