oj.uz

Submission #1055669

# Submission time Handle Problem Language Result Execution time Memory
1055669 2024-08-13T02:50:18 Z efishel Highway Tolls (IOI18_highway) C++17
51 / 100
 143 ms 25960 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;
void dfs (ll u) {
    vis[u] = true;
    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]) continue;
            vis[v] = true; q.push(v);
            adjT[u].push_back({ v, id });
            adjT[v].push_back({ u, id });
        }
    }}
    dfs(0);
    // for (ll i : ord) cout << i << ' ';
    // cout << " ord\n";
    ll u1 = -15, u2 = -15;
    {ll l = -1, r = n-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 = n-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 3 ms 6488 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Correct 2 ms 6488 KB Output is correct
5 Correct 2 ms 6488 KB Output is correct
6 Correct 2 ms 6556 KB Output is correct
7 Correct 3 ms 6488 KB Output is correct
8 Correct 2 ms 6488 KB Output is correct
9 Correct 2 ms 6488 KB Output is correct
10 Correct 2 ms 6488 KB Output is correct
11 Correct 2 ms 6488 KB Output is correct
12 Correct 3 ms 6488 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 10 ms 8088 KB Output is correct
3 Correct 95 ms 19908 KB Output is correct
4 Correct 105 ms 19680 KB Output is correct
5 Correct 84 ms 19680 KB Output is correct
6 Correct 88 ms 19684 KB Output is correct
7 Correct 92 ms 19936 KB Output is correct
8 Correct 91 ms 19936 KB Output is correct
9 Correct 100 ms 19936 KB Output is correct
10 Correct 98 ms 19684 KB Output is correct
11 Correct 101 ms 21220 KB Output is correct
12 Correct 102 ms 21980 KB Output is correct
13 Correct 90 ms 21208 KB Output is correct
14 Correct 101 ms 21280 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8788 KB Output is correct
2 Correct 17 ms 10932 KB Output is correct
3 Correct 24 ms 12956 KB Output is correct
4 Correct 76 ms 25844 KB Output is correct
5 Correct 63 ms 25960 KB Output is correct
6 Correct 72 ms 25800 KB Output is correct
7 Correct 71 ms 25876 KB Output is correct
8 Correct 64 ms 25844 KB Output is correct
9 Correct 78 ms 25892 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 9 ms 8156 KB Output is correct
3 Correct 64 ms 16848 KB Output is correct
4 Correct 88 ms 19676 KB Output is correct
5 Correct 97 ms 19912 KB Output is correct
6 Correct 88 ms 19676 KB Output is correct
7 Correct 84 ms 19680 KB Output is correct
8 Correct 93 ms 19684 KB Output is correct
9 Correct 103 ms 20056 KB Output is correct
10 Correct 84 ms 19688 KB Output is correct
11 Correct 96 ms 20824 KB Output is correct
12 Correct 98 ms 22048 KB Output is correct
13 Correct 97 ms 21528 KB Output is correct
14 Correct 106 ms 21988 KB Output is correct
15 Correct 76 ms 19676 KB Output is correct
16 Correct 79 ms 19740 KB Output is correct
17 Correct 96 ms 21468 KB Output is correct
18 Correct 91 ms 21552 KB Output is correct
19 Correct 79 ms 19884 KB Output is correct
20 Correct 88 ms 22508 KB Output is correct
21 Correct 89 ms 20104 KB Output is correct
22 Correct 72 ms 20120 KB Output is correct
23 Correct 78 ms 19756 KB Output is correct
24 Correct 94 ms 20772 KB Output is correct
25 Correct 91 ms 25356 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8024 KB Output is correct
2 Correct 11 ms 8320 KB Output is correct
3 Correct 117 ms 20428 KB Output is correct
4 Correct 127 ms 20992 KB Output is correct
5 Correct 143 ms 22728 KB Output is correct
6 Correct 124 ms 22220 KB Output is correct
7 Correct 122 ms 22428 KB Output is correct
8 Correct 122 ms 22436 KB Output is correct
9 Correct 94 ms 16996 KB Output is correct
10 Correct 91 ms 17632 KB Output is correct
11 Correct 93 ms 18932 KB Output is correct
12 Correct 120 ms 21100 KB Output is correct
13 Correct 131 ms 21612 KB Output is correct
14 Correct 134 ms 22236 KB Output is correct
15 Correct 128 ms 22380 KB Output is correct
16 Correct 109 ms 18796 KB Output is correct
17 Correct 97 ms 19936 KB Output is correct
18 Correct 75 ms 20260 KB Output is correct
19 Correct 78 ms 20184 KB Output is correct
20 Correct 84 ms 20200 KB Output is correct
21 Incorrect 119 ms 22836 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 12 ms 8024 KB Output is correct
2 Correct 12 ms 8216 KB Output is correct
3 Correct 93 ms 20400 KB Output is correct
4 Partially correct 101 ms 20900 KB Output is partially correct
5 Partially correct 122 ms 20956 KB Output is partially correct
6 Partially correct 130 ms 22228 KB Output is partially correct
7 Correct 103 ms 20472 KB Output is correct
8 Correct 101 ms 20640 KB Output is correct
9 Partially correct 116 ms 21020 KB Output is partially correct
10 Partially correct 124 ms 22320 KB Output is partially correct
11 Partially correct 120 ms 22436 KB Output is partially correct
12 Partially correct 124 ms 22392 KB Output is partially correct
13 Correct 100 ms 18924 KB Output is correct
14 Correct 92 ms 17636 KB Output is correct
15 Correct 96 ms 18952 KB Output is correct
16 Correct 89 ms 17636 KB Output is correct
17 Correct 92 ms 18936 KB Output is correct
18 Correct 107 ms 17636 KB Output is correct
19 Partially correct 115 ms 20928 KB Output is partially correct
20 Partially correct 114 ms 21616 KB Output is partially correct
21 Partially correct 125 ms 22336 KB Output is partially correct
22 Correct 130 ms 22264 KB Output is correct
23 Partially correct 131 ms 22600 KB Output is partially correct
24 Partially correct 139 ms 22252 KB Output is partially correct
25 Partially correct 133 ms 22356 KB Output is partially correct
26 Correct 117 ms 22264 KB Output is correct
27 Correct 83 ms 20168 KB Output is correct
28 Correct 79 ms 19928 KB Output is correct
29 Correct 72 ms 20728 KB Output is correct
30 Correct 85 ms 20180 KB Output is correct
31 Correct 77 ms 20204 KB Output is correct
32 Correct 84 ms 19928 KB Output is correct
33 Partially correct 85 ms 20700 KB Output is partially correct
34 Partially correct 77 ms 20140 KB Output is partially correct
35 Partially correct 76 ms 19928 KB Output is partially correct
36 Partially correct 76 ms 19916 KB Output is partially correct
37 Partially correct 79 ms 20508 KB Output is partially correct
38 Correct 90 ms 20144 KB Output is correct
39 Partially correct 133 ms 23108 KB Output is partially correct
40 Incorrect 122 ms 23304 KB Output is incorrect: {s, t} is wrong.
41 Halted 0 ms 0 KB -