oj.uz

Submission #1055657

# Submission time Handle Problem Language Result Execution time Memory
1055657 2024-08-13T02:26:31 Z efishel Highway Tolls (IOI18_highway) C++17
51 / 100
 101 ms 18676 KB 
#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];
bool vis[MAXN];
ll toPar[MAXN];

vll ord;
void dfs (ll u) {
    vis[u] = true;
    for (auto [v, id] : adj[u]) {
        if (vis[v]) continue;
        dfs(v);
        toPar[v] = id;
    }
    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 dis = ask(vi(m, 0));
    // {ll l = 0, r = n;
    // while (l+1 < r) {
    //     ll mid = (l+r)>>1;
    //     vi vask(m);
    //     for (ll i = 0; i < m; i++) vask[i] = i < mid;
    //     if (ask(vask) == dis) {
    //         ;
    //     }
    // }}
    // todo: make tree
    vi askMask(m, 0);
    dfs(0);
    // for (ll i : ord) cout << i << ' ';
    // cout << " ord\n";
    ll u1 = -15, u2 = -15;
    {ll l = -1, r = m-1;
    // l es normal
    // r lo corta
    while (l+1 < r) {
        ll mid = (l+r)>>1;
        vi vask = askMask;
        for (ll i = 0; i <= mid; i++) vask[toPar[ord[i]]] = 1;
        if (ask(vask) == dis)
            l = mid;
        else
            r = mid;
    }
    u1 = ord[r];}
    fill(vis, vis+MAXN, false);
    ord.clear();
    dfs(u1);
    // for (ll i : ord) cout << i << ' ';
    // cout << " ord\n";
    {ll l = -1, r = m-1;
    // l es normal
    // r lo corta
    while (l+1 < r) {
        ll mid = (l+r)>>1;
        vi vask = askMask;
        for (ll i = 0; i <= mid; i++) vask[toPar[ord[i]]] = 1;
        if (ask(vask) == dis)
            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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 2 ms 3416 KB Output is correct
3 Correct 1 ms 3416 KB Output is correct
4 Correct 1 ms 3416 KB Output is correct
5 Correct 1 ms 3416 KB Output is correct
6 Correct 2 ms 3416 KB Output is correct
7 Correct 1 ms 3416 KB Output is correct
8 Correct 1 ms 3416 KB Output is correct
9 Correct 1 ms 3416 KB Output is correct
10 Correct 2 ms 3416 KB Output is correct
11 Correct 1 ms 3416 KB Output is correct
12 Correct 2 ms 3416 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3672 KB Output is correct
2 Correct 7 ms 4440 KB Output is correct
3 Correct 78 ms 12016 KB Output is correct
4 Correct 80 ms 12020 KB Output is correct
5 Correct 71 ms 12020 KB Output is correct
6 Correct 77 ms 12076 KB Output is correct
7 Correct 73 ms 12272 KB Output is correct
8 Correct 71 ms 12040 KB Output is correct
9 Correct 81 ms 12016 KB Output is correct
10 Correct 74 ms 12168 KB Output is correct
11 Correct 86 ms 13832 KB Output is correct
12 Correct 84 ms 14648 KB Output is correct
13 Correct 72 ms 14064 KB Output is correct
14 Correct 85 ms 14244 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5244 KB Output is correct
2 Correct 17 ms 6892 KB Output is correct
3 Correct 21 ms 8412 KB Output is correct
4 Correct 59 ms 18524 KB Output is correct
5 Correct 62 ms 18548 KB Output is correct
6 Correct 61 ms 18672 KB Output is correct
7 Correct 57 ms 18572 KB Output is correct
8 Correct 57 ms 18676 KB Output is correct
9 Correct 63 ms 18572 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3672 KB Output is correct
2 Correct 8 ms 4440 KB Output is correct
3 Correct 64 ms 10064 KB Output is correct
4 Correct 82 ms 12036 KB Output is correct
5 Correct 74 ms 12020 KB Output is correct
6 Correct 70 ms 12016 KB Output is correct
7 Correct 79 ms 12016 KB Output is correct
8 Correct 75 ms 12164 KB Output is correct
9 Correct 78 ms 12084 KB Output is correct
10 Correct 73 ms 12096 KB Output is correct
11 Correct 90 ms 13516 KB Output is correct
12 Correct 88 ms 14700 KB Output is correct
13 Correct 101 ms 14084 KB Output is correct
14 Correct 85 ms 14700 KB Output is correct
15 Correct 63 ms 12272 KB Output is correct
16 Correct 69 ms 12016 KB Output is correct
17 Correct 91 ms 14320 KB Output is correct
18 Correct 82 ms 14316 KB Output is correct
19 Correct 71 ms 12024 KB Output is correct
20 Correct 82 ms 15344 KB Output is correct
21 Correct 61 ms 12056 KB Output is correct
22 Correct 67 ms 12228 KB Output is correct
23 Correct 64 ms 11832 KB Output is correct
24 Correct 68 ms 12600 KB Output is correct
25 Correct 81 ms 18224 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 4724 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 4696 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -