Submission #587257

#	Time	Username	Problem	Language	Result	Execution time	Memory
587257		Josia	Highway Tolls (IOI18_highway)	C++14	51 / 100	245 ms	21660 KiB

highway

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

using namespace std;

#define int long long

vector<vector<int>> graph;
int normal;
map<pair<int, int>, int> edgeToIndex;

int bsEdges(int M) {
    int l=0; int r = M-1;

    while (l<r) {
        vector<signed> a(M, 0);
        int m = (l + r) / 2;
        for (int i=l; i<=m; i++) {
            a[i] = 1;
        }
        if (ask(a) != normal) {
            r = m;
        }
        else {
            l = m+1;
        }
    }

    return l;
}



vector<int> side;
vector<bool> visited;



void sideDFS(int v) {
    if (visited[v]) return;
    visited[v] = 1;

    side[v] = 1;

    for (int i: graph[v]) {
        sideDFS(i);
    }
}



vector<pair<int, int>> cand;

void findLevel(int v, int t, int l, int p) {
    if (visited[v]) return;
    visited[v] = 1;

    if (l == t) {
        cand.push_back({v, p});
    }

    for (int i: graph[v]) {
        findLevel(i, t, l+1, v);
    }
}



int BS2(vector<pair<int, int>> edges, int M) {
    int l = 0; int r = edges.size()-1;

    while (l<r) {
        vector<signed> a(M, 0);
        int m = (l + r) / 2;
        for (int i=l; i<=m; i++) {
            a[edgeToIndex[{min(edges[i].first, edges[i].second), max(edges[i].first, edges[i].second)}]] = 1;
        }
        if (ask(a) != normal) {
            r = m;
        }
        else {
            l = m+1;
        }
    }

    return edges[l].first;
}



void find_pair(signed N, std::vector<signed> U, std::vector<signed> V, signed A, signed B) {
    int M = U.size();
    assert(M == N-1);

    vector<signed> a(M, 0);
    normal = ask(a);

    vector<pair<int, int>> edges;
    graph.clear();
    graph.resize(N);

    edgeToIndex.clear();

    for (int i=0; i<M; i++) {
        edges.push_back({min(U[i], V[i]), max(U[i], V[i])});
        graph[U[i]].push_back(V[i]);
        graph[V[i]].push_back(U[i]);
        edgeToIndex[{min(U[i], V[i]), max(U[i], V[i])}] = i;
    }

    pair<int, int> edgeOnPath = edges[bsEdges(M)];


    side.assign(N, 0);
    visited.assign(N, 0);

    visited[edgeOnPath.second] = 1;
    sideDFS(edgeOnPath.first);

    pair<int, int> length;

    {
        vector<signed> askk(M, 0);
        for (int i=0; i<M; i++) {
            if (side[edges[i].first] && side[edges[i].second]) askk[i] = 1;
        }
        int tmp = ask(askk);


        length.first = ((tmp-normal)/(B-A));
        length.second = ((normal - (length.first * A)) / A) -1;
    }


    visited.assign(N, 0);
    cand.clear();

    visited[edgeOnPath.second] = 1;

    findLevel(edgeOnPath.first, length.first, 0, -1);


    int start = BS2(cand, M);



    visited.assign(N, 0);
    cand.clear();

    visited[edgeOnPath.first] = 1;

    findLevel(edgeOnPath.second, length.second, 0, -1);

    int end = BS2(cand, M);



    answer(min(start, end), max(start, end));
}

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