Submission #139375

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
139375	2019-07-31T15:28:56 Z	fredbr	Highway Tolls (IOI18_highway)	C++17	18 / 100	384 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 (i != U[order[l]] and i != V[order[l]] and
                i != U[order[r]] and i != V[order[r]]) continue;

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

    // cout << vt[l] <<" " << vt[r] << "\n";
    // cout << a << " " << b << "\n";

    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	5 ms	2424 KB	Output is correct
3	Correct	4 ms	2424 KB	Output is correct
4	Correct	5 ms	2424 KB	Output is correct
5	Correct	4 ms	2428 KB	Output is correct
6	Correct	4 ms	2428 KB	Output is correct
7	Correct	4 ms	2424 KB	Output is correct
8	Correct	4 ms	2424 KB	Output is correct
9	Correct	4 ms	2424 KB	Output is correct
10	Correct	4 ms	2428 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	20 ms	3164 KB	Output is correct
3	Correct	178 ms	9024 KB	Output is correct
4	Correct	238 ms	9124 KB	Output is correct
5	Correct	205 ms	9348 KB	Output is correct
6	Correct	195 ms	9008 KB	Output is correct
7	Correct	209 ms	9024 KB	Output is correct
8	Correct	174 ms	9264 KB	Output is correct
9	Correct	192 ms	9028 KB	Output is correct
10	Correct	222 ms	9028 KB	Output is correct
11	Correct	219 ms	10280 KB	Output is correct
12	Correct	222 ms	11136 KB	Output is correct
13	Correct	212 ms	10308 KB	Output is correct
14	Correct	203 ms	9640 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	3904 KB	Output is correct
2	Correct	29 ms	5452 KB	Output is correct
3	Correct	55 ms	6828 KB	Output is correct
4	Correct	183 ms	15504 KB	Output is correct
5	Correct	182 ms	15524 KB	Output is correct
6	Correct	181 ms	15500 KB	Output is correct
7	Correct	205 ms	15528 KB	Output is correct
8	Correct	153 ms	15504 KB	Output is correct
9	Correct	164 ms	15580 KB	Output is correct