Submission #139348

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
139348	2019-07-31T15:05:54 Z	fredbr	Highway Tolls (IOI18_highway)	C++17	18 / 100	358 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;

void dfs(int x, int p) {
    for (Edge e : v[x]) {
        if (e.u == p) continue;
        order.push_back(e.id);
        dfs(e.u, x);
        // 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 = -1, r = (int)order.size()-1;

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

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

        ll cost = ask(q);

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

    l = old_l;

    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;
        }
    }

    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	2364 KB	Output is correct
5	Correct	4 ms	2352 KB	Output is correct
6	Correct	4 ms	2424 KB	Output is correct
7	Correct	5 ms	2424 KB	Output is correct
8	Correct	5 ms	2424 KB	Output is correct
9	Correct	5 ms	2424 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	2552 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	2472 KB	Output is correct
2	Correct	23 ms	3000 KB	Output is correct
3	Correct	190 ms	8040 KB	Output is correct
4	Correct	202 ms	8008 KB	Output is correct
5	Correct	194 ms	8020 KB	Output is correct
6	Correct	177 ms	8016 KB	Output is correct
7	Correct	216 ms	8164 KB	Output is correct
8	Correct	159 ms	8020 KB	Output is correct
9	Correct	189 ms	7976 KB	Output is correct
10	Correct	145 ms	8020 KB	Output is correct
11	Correct	201 ms	8780 KB	Output is correct
12	Correct	195 ms	9488 KB	Output is correct
13	Correct	194 ms	8992 KB	Output is correct
14	Correct	186 ms	8456 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	3552 KB	Output is correct
2	Correct	60 ms	4844 KB	Output is correct
3	Correct	73 ms	5996 KB	Output is correct
4	Correct	150 ms	13156 KB	Output is correct
5	Correct	173 ms	13136 KB	Output is correct
6	Correct	162 ms	13056 KB	Output is correct
7	Correct	223 ms	13140 KB	Output is correct
8	Correct	241 ms	13140 KB	Output is correct
9	Correct	169 ms	13128 KB	Output is correct