Submission #139378

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
139378	2019-07-31T15:30:44 Z	fredbr	Highway Tolls (IOI18_highway)	C++17	18 / 100	396 ms	262148 KB

highway

#include "highway.h"

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int const maxn = 90909;

struct Edge {
    int u, id;
};

vector<Edge> v[maxn];

vector<int> order;
vector<int> vt;

void dfs(int x, int p) {
    for (Edge e : v[x]) {
        if (e.u == p) continue;
        order.push_back(e.id);
        vt.push_back(x);
        dfs(e.u, x);
        vt.push_back(e.u);
        order.push_back(e.id);
    }
}

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++) {
        v[U[i]].push_back(Edge{V[i], i});
        v[V[i]].push_back(Edge{U[i], i});
    }

    dfs(0, 0);

    ll total_cost = ask(vector<int>(m, 0));

    int l = 0, r = order.size();

    while (r-l > 1) {
        int mid = (l+r)/2;

        vector<int> q(m);
        for (int i = 0; i < mid; i++)
            q[order[i]] = 1;

        ll cost = ask(q);

        if (cost == total_cost) l = mid;
        else r = mid;
    }

    int old_l = l;

    l = 0, r = (int)order.size();

    while (r-l > 1) {
        int mid = (l+r)/2;

        vector<int> q(m);
        for (int i = mid; i < (int)order.size(); i++)
            q[order[i]]++;

        for (int& i : q) {
            if (i == 2) i = 1;
            else i = 0;
        }

        ll cost = ask(q);

        if (cost == total_cost) r = mid;
        else l = mid;
    }

    r = l;
    l = old_l;

    // for (int i : order) cout << i << " ";
    // cout << "\n";

    // cout << l << " " << r << "\n";
    vector<int> cnt(n);

    for (int i = l; i <= r; i++) {
        cnt[U[order[i]]]++;
        cnt[V[order[i]]]++;
    }

    a = -1, b = -1;

    for (int i = 0; i < n; i++) {
        if (cnt[i] == 1) {

            if (a == -1) a = i;
            else b= i;
        }
    }

    if (a > b) swap(a, b);
    answer(a, b);
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	2424 KB	Output is correct
2	Correct	4 ms	2424 KB	Output is correct
3	Correct	4 ms	2424 KB	Output is correct
4	Correct	4 ms	2424 KB	Output is correct
5	Correct	4 ms	2424 KB	Output is correct
6	Correct	4 ms	2468 KB	Output is correct
7	Correct	4 ms	2344 KB	Output is correct
8	Correct	4 ms	2424 KB	Output is correct
9	Correct	4 ms	2348 KB	Output is correct
10	Correct	4 ms	2424 KB	Output is correct
11	Correct	4 ms	2424 KB	Output is correct
12	Correct	4 ms	2424 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	2424 KB	Output is correct
2	Correct	25 ms	3192 KB	Output is correct
3	Correct	175 ms	9016 KB	Output is correct
4	Correct	185 ms	9008 KB	Output is correct
5	Correct	191 ms	9356 KB	Output is correct
6	Correct	169 ms	8996 KB	Output is correct
7	Correct	191 ms	9012 KB	Output is correct
8	Correct	218 ms	9308 KB	Output is correct
9	Correct	179 ms	9016 KB	Output is correct
10	Correct	176 ms	9064 KB	Output is correct
11	Correct	168 ms	10164 KB	Output is correct
12	Correct	209 ms	11228 KB	Output is correct
13	Correct	226 ms	10320 KB	Output is correct
14	Correct	215 ms	9664 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	3932 KB	Output is correct
2	Correct	28 ms	5428 KB	Output is correct
3	Correct	31 ms	6808 KB	Output is correct
4	Correct	160 ms	15592 KB	Output is correct
5	Correct	143 ms	15624 KB	Output is correct
6	Correct	163 ms	15528 KB	Output is correct
7	Correct	157 ms	15492 KB	Output is correct
8	Correct	166 ms	15516 KB	Output is correct
9	Correct	143 ms	15512 KB	Output is correct