Submission #1232194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232194		VMaksimoski008	통행료 (IOI18_highway)	C++20	12 / 100	59 ms	14248 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int mxn = 9e4 + 5;

vector<int> mn(mxn, 1e9), ord_id(mxn, 1e9);
vector<pii> g1[mxn], g[mxn];

void dfs(int u) {
    for(auto [v, id] : g[u]) {
        dfs(v);
        mn[id] = ord_id[v];
        ord_id[u] = min(ord_id[u], ord_id[v]);
    }
}

void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
    ll len = 0, m = U.size();
    vector<int> dummy(m);
    len = ask(dummy) / A;

    queue<int> q;

    for(int i=0; i<m; i++) {
        g1[U[i]].push_back({ V[i], i });
        g1[V[i]].push_back({ U[i], i });
    }

    q.push(0);
    vector<int> dist(n, -1), ord;
    dist[0] = 0;

    int curr = 0;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        if(dist[u] == len) {
            ord_id[u] = curr++;
            ord.push_back(u);
            continue;
        }

        for(auto [v, id] : g1[u]) {
            if(dist[v] != -1) continue;
            dist[v] = dist[u] + 1;
            q.push(v);
            g[u].push_back({ v, id });
        }
    }

    dfs(0);

    int l=0, r=ord.size()-1, p=0;
    while(l <= r) {
        int mid = (l + r) / 2;
        vector<int> to_get(m, 1);
        for(int i=0; i<m; i++)
            if(mn[i] <= mid) to_get[i] = 0;
        
        ll res = ask(to_get);
        if(res == (ll)len * A) p = mid, r = mid - 1;
        else l = mid + 1;
    }

    answer(0, ord[p]);
}

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