Submission #1199073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199073		theyeia	Highway Tolls (IOI18_highway)	C++20	12 / 100	773 ms	327680 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
const int MOD = 1e9 + 7;
#define F first
#define S second
#define sz(x) int((x).size())
#define sor(x) sort(begin(x), end(x))
#define FOR(i, a, b) for (int i = a; i < b; i++)

map<int,vector<pi>> Adj;
vi Anc, Candidates;
vector<ll> Depths;
ll depth;

void dfs(int u, int pre) {
    Depths[u] = Depths[pre] + 1;

    if (Depths[u] == depth) Candidates.push_back(u);

    for (auto v : Adj[u]) {
        if (v.F == pre) continue;
        Anc[v.F] = v.S;
        dfs(v.F, u);
    }
}

void find_pair(int n, vi U, vi V, int a, int b) {
    int m = U.size();

    int s = 0;

    vi traffic(m, 0);
    depth = ask(traffic) / (ll)a;
    //cout << "depth is " << depth << endl;

    Depths.resize(n, -1);
    Anc.resize(n);
    Anc[0] = -1;

    FOR(i, 0, m) {
        Adj[U[i]].push_back({V[i],i});
        Adj[V[i]].push_back({U[i],i});
    }

    dfs(0, 0);

    //for (auto anc : Anc) cout << anc << " "; cout << endl;
    //for (auto d : Depths) cout << d << " "; cout << endl;

    while (sz(Candidates) > 1) {
        //for (auto c : Candidates) cout << c << " "; cout << "oink" << endl;

        vi traffic(m, 0), Left, Right;

        int k = sz(Candidates);

        FOR(i, 0, k / 2) {
            traffic[Anc[Candidates[i]]] = 1;
            Left.push_back(Candidates[i]);
        }
        FOR(i, k / 2, k) {
            Right.push_back(Candidates[i]);
        }

        ll toll = ask(traffic);

        if (toll > depth * (ll)a) {
            Candidates = Left;
        }
        else {
            Candidates = Right;
        }
    }

    answer(s, Candidates[0]);
}

//#include "grader.cpp"

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