Submission #864521

#	Time	Username	Problem	Language	Result	Execution time	Memory
864521		thinknoexit	Highway Tolls (IOI18_highway)	C++17	51 / 100	97 ms	14580 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
using ll = long long;
const int N = 90090;
vector<pair<int, int>> adj[N], e;
int n;
int p[N], sz[N];
int fr(int i) {
    return (p[i] == i) ? i : p[i] = fr(p[i]);
}
void dfs(int v, int p = -1) {
    for (auto& x : adj[v]) {
        if (x.first == p) continue;
        e.push_back({ x.second, x.first });
        dfs(x.first, v);
    }
}
void find_pair(int NN, vector<int> U, vector<int> V, int A, int B) {
    n = NN;
    int m = U.size();
    for (int i = 0;i < n;i++) p[i] = i;
    for (int i = 0;i < m;i++) {
        int u = U[i], v = V[i];
        int pu = fr(u), pv = fr(v);
        if (pu != pv) {
            adj[u].push_back({ v,i });
            adj[v].push_back({ u,i });
            p[pu] = pv;
        }
    }
    vector<int> QQ(m, 0);
    ll mnp = ask(QQ);
    dfs(0);
    int l = 1, r = n - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        vector<int> q(m, 1);
        for (int i = 0;i < mid;i++) {
            q[e[i].first] = 0;
        }
        if (ask(q) == mnp) r = mid;
        else l = mid + 1;
    }
    int city2 = e[l - 1].second;
    e.clear();
    dfs(city2);
    l = 1, r = n - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        vector<int> q(m, 1);
        for (int i = 0;i < mid;i++) {
            q[e[i].first] = 0;
        }
        if (ask(q) == mnp) r = mid;
        else l = mid + 1;
    }
    int city1 = e[l - 1].second;
    answer(city1, city2);
}

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