Submission #1217459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217459		perekopskad	Highway Tolls (IOI18_highway)	C++20	12 / 100	74 ms	18576 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define el '\n'
#define pb push_back
#define pii pair <ll, ll>
#define ff first
#define ss second
#define mkp make_pair
#define fr(i, l, r) for(ll (i) = l; (i) <= r; (i)++)
#define frb(i, r, l) for(ll (i) = r; (i) >= l; (i)--)

template<class T, class S>
inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}

template<class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}

ll const N = 1e5 + 10;
ll const LOG = 22;
ll const inf = 1e9 + 10;
ll const INF = 1e18 + 10;
ll const mod = 1e9 + 7;
ll const mod2 = 998244353;
ll const K = 400;

ll m;
vector <pii> g[N];
vector <int> w;
ll par[N], idup[N], tin[N], pos[N], used[N];
ll timer = 0, start;

void dfs(ll v, ll p) {
    tin[v] = ++timer;
    pos[tin[v]] = v;
    par[v] = p;
    for(auto [u, id] : g[v]) {
        if(u != p) {
            idup[u] = id;
            dfs(u, v);
        }
    }
}

ll check(ll l, ll r) {
    fill(w.begin(), w.end(), 0);
    fill(used, used + N, 0);

    fr(x, l, r) {
        ll v = pos[x];
        while(v && !used[v]) {
            used[v] = 1;
            w[idup[v]] = 1;
            v = par[v];
        }
    }

    return ask(w);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    m = U.size();
    for(int i = 0; i < m; i++) {
        g[U[i]].pb({V[i], i});
        g[V[i]].pb({U[i], i});
    }
    w.resize(m);

    start = ask(w) / A;

    dfs(0, 0);

    ll bl = 1, br = N;
    while(bl < br) {
        ll mid = (bl + br) / 2;
        if(check(bl, mid) == start * B)
            br = mid;
        else 
            bl = mid + 1;
    }

    answer(0, pos[bl]);
}

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