oj.uz

Submission #1057591

# Submission time Handle Problem Language Result Execution time Memory
1057591 2024-08-13T22:47:07 Z efishel Highway Tolls (IOI18_highway) C++17
51 / 100
 151 ms 25648 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];
vii adjT[MAXN];
bool vis[MAXN];
ll toPar[MAXN];

vll ord;
ll cvis;
void dfs (ll u) {
    vis[u] = true; cvis++;
    for (auto [v, id] : adjT[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));
    vi askMask(m, 0);
    ll src1 = -15, src2 = -15;
    {ll l = -1, r = m-1;
    while (l+1 < r) {
        ll mid = (l+r)>>1;
        askMask = vi(m, 0);
        for (ll i = 0; i <= mid; i++) askMask[i] = 1;
        if (ask(askMask) == dis)
            l = mid;
        else
            r = mid;
    }
    askMask = vi(m, 0);
    for (ll i = 0; i <= l; i++) askMask[i] = 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 });
    while (q.size()) {
        ll u = q.front(); q.pop();
        for (auto [v, id] : adj[u]) {
            if (vis[v] || askMask[id] == 1) continue;
            vis[v] = true; q.push(v);
            adjT[u].push_back({ v, id });
            adjT[v].push_back({ u, id });
        }
    }}
    cvis = 0;
    dfs(src1);
    // for (ll i : ord) cout << i << ' ';
    // cout << " ord\n";
    ll u1 = -15, u2 = -15;
    {ll l = -1, r = cvis-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();
    cvis = 0;
    dfs(u1);
    // for (ll i : ord) cout << i << ' ';
    // cout << " ord\n";
    {ll l = -1, r = cvis-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 7512 KB Output is correct
2 Correct 1 ms 7512 KB Output is correct
3 Correct 2 ms 7512 KB Output is correct
4 Correct 1 ms 7512 KB Output is correct
5 Correct 1 ms 7512 KB Output is correct
6 Correct 1 ms 7340 KB Output is correct
7 Correct 1 ms 7512 KB Output is correct
8 Correct 1 ms 7512 KB Output is correct
9 Correct 1 ms 7512 KB Output is correct
10 Correct 1 ms 7512 KB Output is correct
11 Correct 2 ms 7512 KB Output is correct
12 Correct 1 ms 7512 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 10 ms 9040 KB Output is correct
3 Correct 87 ms 19172 KB Output is correct
4 Correct 79 ms 19116 KB Output is correct
5 Correct 87 ms 20136 KB Output is correct
6 Correct 76 ms 17408 KB Output is correct
7 Correct 90 ms 16960 KB Output is correct
8 Correct 94 ms 20192 KB Output is correct
9 Correct 74 ms 17124 KB Output is correct
10 Correct 83 ms 18448 KB Output is correct
11 Correct 68 ms 15756 KB Output is correct
12 Correct 86 ms 21420 KB Output is correct
13 Correct 82 ms 21476 KB Output is correct
14 Correct 90 ms 21656 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9304 KB Output is correct
2 Correct 14 ms 11308 KB Output is correct
3 Correct 19 ms 10024 KB Output is correct
4 Correct 60 ms 21444 KB Output is correct
5 Correct 62 ms 21564 KB Output is correct
6 Correct 62 ms 23936 KB Output is correct
7 Correct 64 ms 14620 KB Output is correct
8 Correct 56 ms 22528 KB Output is correct
9 Correct 58 ms 17220 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7508 KB Output is correct
2 Correct 7 ms 8536 KB Output is correct
3 Correct 57 ms 17196 KB Output is correct
4 Correct 82 ms 18856 KB Output is correct
5 Correct 58 ms 14764 KB Output is correct
6 Correct 59 ms 14516 KB Output is correct
7 Correct 75 ms 16928 KB Output is correct
8 Correct 65 ms 14920 KB Output is correct
9 Correct 86 ms 19428 KB Output is correct
10 Correct 78 ms 17844 KB Output is correct
11 Correct 104 ms 20980 KB Output is correct
12 Correct 92 ms 21484 KB Output is correct
13 Correct 84 ms 20116 KB Output is correct
14 Correct 70 ms 16628 KB Output is correct
15 Correct 56 ms 14768 KB Output is correct
16 Correct 55 ms 14260 KB Output is correct
17 Correct 94 ms 20816 KB Output is correct
18 Correct 89 ms 21860 KB Output is correct
19 Correct 57 ms 14260 KB Output is correct
20 Correct 60 ms 14820 KB Output is correct
21 Correct 69 ms 17636 KB Output is correct
22 Correct 60 ms 15804 KB Output is correct
23 Correct 77 ms 20184 KB Output is correct
24 Correct 82 ms 20828 KB Output is correct
25 Correct 85 ms 25648 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8868 KB Output is correct
2 Correct 10 ms 8888 KB Output is correct
3 Correct 96 ms 20792 KB Output is correct
4 Correct 99 ms 20492 KB Output is correct
5 Correct 109 ms 21996 KB Output is correct
6 Correct 117 ms 22684 KB Output is correct
7 Correct 123 ms 22412 KB Output is correct
8 Correct 108 ms 22124 KB Output is correct
9 Correct 90 ms 15704 KB Output is correct
10 Correct 85 ms 18284 KB Output is correct
11 Correct 95 ms 19028 KB Output is correct
12 Correct 117 ms 21560 KB Output is correct
13 Correct 104 ms 22088 KB Output is correct
14 Correct 145 ms 22648 KB Output is correct
15 Correct 141 ms 22576 KB Output is correct
16 Correct 108 ms 19440 KB Output is correct
17 Correct 68 ms 18056 KB Output is correct
18 Correct 63 ms 15476 KB Output is correct
19 Correct 77 ms 19676 KB Output is correct
20 Correct 63 ms 16764 KB Output is correct
21 Incorrect 120 ms 23092 KB Output is incorrect: {s, t} is wrong.
22 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9048 KB Output is correct
2 Correct 10 ms 9048 KB Output is correct
3 Correct 98 ms 20692 KB Output is correct
4 Correct 86 ms 20916 KB Output is correct
5 Partially correct 111 ms 21200 KB Output is partially correct
6 Partially correct 110 ms 22276 KB Output is partially correct
7 Correct 111 ms 20684 KB Output is correct
8 Partially correct 99 ms 21016 KB Output is partially correct
9 Partially correct 94 ms 20868 KB Output is partially correct
10 Correct 122 ms 22412 KB Output is correct
11 Partially correct 121 ms 22596 KB Output is partially correct
12 Correct 120 ms 22592 KB Output is correct
13 Correct 76 ms 16648 KB Output is correct
14 Correct 86 ms 17084 KB Output is correct
15 Correct 91 ms 19612 KB Output is correct
16 Correct 92 ms 18268 KB Output is correct
17 Correct 88 ms 18976 KB Output is correct
18 Correct 87 ms 18380 KB Output is correct
19 Correct 110 ms 21556 KB Output is correct
20 Partially correct 112 ms 22068 KB Output is partially correct
21 Correct 112 ms 22588 KB Output is correct
22 Partially correct 121 ms 22588 KB Output is partially correct
23 Correct 126 ms 22696 KB Output is correct
24 Partially correct 151 ms 22584 KB Output is partially correct
25 Partially correct 115 ms 22276 KB Output is partially correct
26 Correct 141 ms 22596 KB Output is correct
27 Correct 64 ms 16908 KB Output is correct
28 Correct 72 ms 19232 KB Output is correct
29 Correct 75 ms 20876 KB Output is correct
30 Correct 78 ms 20104 KB Output is correct
31 Correct 90 ms 19424 KB Output is correct
32 Correct 79 ms 19380 KB Output is correct
33 Partially correct 78 ms 20872 KB Output is partially correct
34 Correct 75 ms 18668 KB Output is correct
35 Correct 81 ms 18680 KB Output is correct
36 Partially correct 97 ms 19680 KB Output is partially correct
37 Correct 71 ms 19688 KB Output is correct
38 Correct 83 ms 19984 KB Output is correct
39 Partially correct 138 ms 23444 KB Output is partially correct
40 Incorrect 141 ms 23812 KB Output is incorrect: {s, t} is wrong.
41 Halted 0 ms 0 KB -