Submission #738150

#	Time	Username	Problem	Language	Result	Execution time	Memory
738150		PixelCat	Highway Tolls (IOI18_highway)	C++14	100 / 100	253 ms	11924 KiB

highway

#ifdef NYAOWO
#include "grader.cpp"
#endif
#include "highway.h"

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 90010;

vector<pii> adj[MAXN]; // index, eid
int dep[MAXN];
int eid[MAXN];
int typ[MAXN];

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    cerr << A << " " << B << "\n";
    int M = U.size();
    LL dist = ask(vector<int>(M, 0));
    assert(dist % A == 0);
    auto out = [&](int x) { cerr << "(" << U[x] << ", " << V[x] << ")\n" << flush; };

    For(i, 0, M - 1) {
        adj[U[i]].eb(V[i], i);
        adj[V[i]].eb(U[i], i);
    }
    int hi = M - 1, lo = -1;
    while(hi - lo > 1) {
        int mi = lo + (hi - lo) / 2;
        vector<int> w(M, 0);
        fill(w.begin(), w.begin() + mi + 1, 1);
        LL d2 = ask(w);
        if(d2 > dist) hi = mi;
        else lo = mi;
    }
    int a = U[hi], b = V[hi];
    cerr << "key edge: " << hi << " "; out(hi);
    
    // build bfs tree
    memset(typ, -1, sizeof(typ));
    queue<int> que;
    dep[a] = 1; dep[b] = 1;
    eid[a] = eid[b] = hi;
    typ[a] = 0; typ[b] = 1;
    que.emplace(a); que.emplace(b);
    vector<int> ed[2];
    vector<int> w0(M, 1);
    while(!que.empty()) {
        int cur = que.front(); que.pop();
        w0[eid[cur]] = 0;
        ed[typ[cur]].eb(eid[cur]);
        for(auto &e:adj[cur]) if(typ[e.F] == -1 && e.S >= hi) {
            dep[e.F] = dep[cur] + 1;
            eid[e.F] = e.S;
            typ[e.F] = typ[cur];
            que.emplace(e.F);
        }
    }
    // cerr << "bfs tree #0\n"; for(auto &id:ed[0]) out(id);
    // cerr << "bfs tree #1\n"; for(auto &id:ed[1]) out(id);

    int m = sz(ed[0]);
    hi = m; lo = -1;
    while(hi - lo > 1) {
        int mi = lo + (hi - lo) / 2;
        vector<int> w(all(w0));
        For(i, mi, m - 1) w[ed[0][i]] = 1;
        auto d2 = ask(w);
        if(d2 == dist) hi = mi;
        else lo = mi;
    }
    dep[b] = 0;
    int id = ed[0][lo];
    int x0 = U[id];
    if(dep[V[id]] > dep[U[id]]) x0 = V[id];
    cerr << "x0: " << x0 << "\n";
    dep[b] = 1;

    m = sz(ed[1]);
    hi = m; lo = -1;
    while(hi - lo > 1) {
        int mi = lo + (hi - lo) / 2;
        vector<int> w(all(w0));
        For(i, mi, m - 1) w[ed[1][i]] = 1;
        auto d2 = ask(w);
        if(d2 == dist) hi = mi;
        else lo = mi;
    }
    dep[a] = 0;
    id = ed[1][lo];
    int x1 = U[id];
    if(dep[V[id]] > dep[U[id]]) x1 = V[id];
    cerr << "x1: " << x1 << "\n";
    dep[a] = 1;

    answer(x0, x1);

    // for (int j = 0; j < 50; ++j) {
    //     std::vector<int> w(M);
    //     for (int i = 0; i < M; ++i) {
    //         w[i] = 0;
    //     }
    //     long long toll = ask(w);
    // }
    // answer(0, N - 1);
}

/*

4 4 1 3 1 3
0 1
0 2
0 3
1 2

*/

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