Submission #1057604

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1057604	2024-08-13T23:54:18 Z	efishel	Highway Tolls (IOI18_highway)	C++17	6 / 100	316 ms	24688 KB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

const ll MAXN = 1.3E5+16;
vii adj[MAXN];
vii adjT[MAXN];
bool vis[MAXN];
ll toPar[MAXN];
ll dep[MAXN];
ll dis;

vll ord;
void dfs (ll u) {
    vis[u] = true;
    for (auto [v, id] : adjT[u]) {
        if (vis[v]) continue;
        dep[v] = dep[u]+1;
        dfs(v);
        toPar[v] = id;
    }
    if (dep[u] == dis) ord.push_back(u);
}

void find_pair (int n, vi us, vi vs, int a, int b) {
    ll m = us.size();
    for (ll i = 0; i < m; i++) {
        adj[us[i]].push_back({ vs[i], i });
        adj[vs[i]].push_back({ us[i], i });
    }
    ll raw = ask(vi(m, 0));
    dis = raw/a;
    vi askMask(m, -15);
    ll src1 = -15, src2 = -15;
    {ll l = -1, r = m-1;
    while (l+1 < r) {
        ll mid = (l+r)>>1;
        vi vask(m, 0);
        for (ll i = 0; i <= mid; i++) vask[i] = 1;
        if (ask(vask) == raw)
            l = mid;
        else
            r = mid;
    }
    askMask = vi(m, 1);
    src1 = us[r];
    src2 = vs[r];
    queue <ll> q;
    vector <char> vis(n, false);
    vis[src1] = true; q.push(src1);
    vis[src2] = true; q.push(src2);
    adjT[src1].push_back({ src2, r });
    adjT[src2].push_back({ src1, r });
    askMask[r] = 0;
    while (q.size()) {
        ll u = q.front(); q.pop();
        for (auto [v, id] : adj[u]) {
            if (vis[v] || id <= l) continue;
            vis[v] = true; q.push(v);
            cerr << u << ' ' << v << '\n';
            adjT[u].push_back({ v, id });
            adjT[v].push_back({ u, id });
            askMask[id] = 0;
        }
    }}
    dep[src1] = 0;
    dfs(src1);
    // for (ll i : askMask) cout << i << ' ';
    // cout << " askMask\n";
    // for (ll i : ord) cout << i << ' ';
    // cout << " ord\n";
    // for (ll i : ord) cout << toPar[i] << ' ';
    // cout << " par[ord]\n";
    ll u1 = -15, u2 = -15;
    {ll l = -1, r = ord.size();
    // l es normal
    // r lo corta
    while (l+1 < r) {
        ll mid = (l+r)>>1;
        vi vask(askMask.begin(), askMask.end());
        for (ll i = 0; i <= mid; i++) vask[toPar[ord[i]]] = 1;
        if (ask(vask) == raw)
            l = mid;
        else
            r = mid;
    }
    u1 = ord[r];}
    // cout << u1 << " u1\n";
    fill(vis, vis+MAXN, false);
    ord.clear();
    dep[u1] = 0;
    dfs(u1);
    // for (ll i : ord) cout << i << ' ';
    // cout << " ord\n";
    {ll l = -1, r = ord.size();
    // l es normal
    // r lo corta
    while (l+1 < r) {
        ll mid = (l+r)>>1;
        vi vask(askMask.begin(), askMask.end());
        for (ll i = 0; i <= mid; i++) vask[toPar[ord[i]]] = 1;
        if (ask(vask) == raw)
            l = mid;
        else
            r = mid;
    }
    // cout << "l, r: " << l << ' ' << r << '\n';
    // cout << "ord[l, r]: " << ord[l] << ' ' << ord[r] << '\n';
    u2 = ord[r];}
    // cout << "u1 " << u1 << '\n';
    // cout << "u2 " << u2 << '\n';
    answer(u1, u2);
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	8536 KB	Output is correct
2	Correct	2 ms	8536 KB	Output is correct
3	Runtime error	8 ms	16984 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	8536 KB	Output is correct
2	Correct	40 ms	9880 KB	Output is correct
3	Correct	314 ms	20052 KB	Output is correct
4	Incorrect	310 ms	19860 KB	Output is incorrect: {s, t} is wrong.
5	Halted	0 ms	0 KB	-

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	10340 KB	Output is correct
2	Correct	66 ms	12268 KB	Output is correct
3	Correct	31 ms	11036 KB	Output is correct
4	Correct	239 ms	22664 KB	Output is correct
5	Correct	244 ms	22796 KB	Output is correct
6	Correct	316 ms	24688 KB	Output is correct
7	Correct	66 ms	15604 KB	Output is correct
8	Correct	260 ms	23504 KB	Output is correct
9	Correct	139 ms	17920 KB	Output is correct