Submission #434547

#	Time	Username	Problem	Language	Result	Execution time	Memory
434547		dxz05	Highway Tolls (IOI18_highway)	C++14	12 / 100	197 ms	59196 KiB

highway

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

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 3e2;

vector<int> g[MAXN];
int p[MAXN], d[MAXN];
vector<int> vec[MAXN];
int edgeID[MAXN];

void dfs(int v, int par, int dep){
    p[v] = par;
    d[v] = dep;
    vec[dep].push_back(v);

    for (int u : g[v]){
        if (u != par) dfs(u, v, dep + 1);
    }
}

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

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

    dfs(0, -1, 0);

    for (int i = 0; i < M; i++){
        if (p[U[i]] == V[i]) swap(U[i], V[i]);
        edgeID[V[i]] = i;
    }

    ll onlyA = ask(w);

    int dep = 0;

    int l = 1, r = N - 1;
    while (l <= r){
        int m = (l + r) >> 1;
        for (int i = 0; i < M; i++){
            w[i] = (d[V[i]] > m);
        }

        ll res = ask(w);

        if (res == onlyA){
            dep = m;
            r = m - 1;
        } else l = m + 1;

    }

    int T = 0;

    l = 0, r = vec[dep].size() - 1;
    while (l <= r){
        int m = (l + r) >> 1;
        fill(w.begin(), w.end(), 0);

        for (int i = 0; i < m; i++){
            w[edgeID[vec[dep][i]]] = 1;
        }

        if (ask(w) == onlyA){
            T = vec[dep][m];
            l = m + 1;
        } else r = m - 1;
    }


    answer(0, T);
}
/**
12 11 3 5 0 9
0 1
0 2
1 3
1 4
4 5
2 6
2 7
2 8
7 9
7 10
9 11
*/

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