oj.uz

Submission #1055661

# Submission time Handle Problem Language Result Execution time Memory
1055661 2024-08-13T02:41:27 Z efishel Highway Tolls (IOI18_highway) C++17
51 / 100
 149 ms 35124 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 = 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 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 3 ms 6488 KB Output is correct
6 Correct 3 ms 6488 KB Output is correct
7 Correct 2 ms 6488 KB Output is correct
8 Correct 2 ms 6488 KB Output is correct
9 Correct 3 ms 6488 KB Output is correct
10 Correct 3 ms 6488 KB Output is correct
11 Correct 3 ms 6488 KB Output is correct
12 Correct 2 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 8028 KB Output is correct
3 Correct 102 ms 19688 KB Output is correct
4 Correct 98 ms 19720 KB Output is correct
5 Correct 86 ms 19856 KB Output is correct
6 Correct 89 ms 19692 KB Output is correct
7 Correct 87 ms 19852 KB Output is correct
8 Correct 83 ms 19680 KB Output is correct
9 Correct 111 ms 19932 KB Output is correct
10 Correct 88 ms 19680 KB Output is correct
11 Correct 99 ms 21372 KB Output is correct
12 Correct 97 ms 21996 KB Output is correct
13 Correct 92 ms 21216 KB Output is correct
14 Correct 103 ms 21280 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8788 KB Output is correct
2 Correct 17 ms 10932 KB Output is correct
3 Correct 24 ms 13112 KB Output is correct
4 Correct 67 ms 25972 KB Output is correct
5 Correct 70 ms 25856 KB Output is correct
6 Correct 73 ms 25784 KB Output is correct
7 Correct 72 ms 25880 KB Output is correct
8 Correct 73 ms 26300 KB Output is correct
9 Correct 91 ms 25884 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 11 ms 8164 KB Output is correct
3 Correct 65 ms 16720 KB Output is correct
4 Correct 83 ms 19672 KB Output is correct
5 Correct 95 ms 19920 KB Output is correct
6 Correct 78 ms 19688 KB Output is correct
7 Correct 81 ms 19676 KB Output is correct
8 Correct 91 ms 19676 KB Output is correct
9 Correct 94 ms 19668 KB Output is correct
10 Correct 88 ms 19888 KB Output is correct
11 Correct 116 ms 21016 KB Output is correct
12 Correct 100 ms 21984 KB Output is correct
13 Correct 111 ms 21528 KB Output is correct
14 Correct 97 ms 21992 KB Output is correct
15 Correct 81 ms 19680 KB Output is correct
16 Correct 79 ms 19820 KB Output is correct
17 Correct 93 ms 21472 KB Output is correct
18 Correct 89 ms 21560 KB Output is correct
19 Correct 73 ms 19888 KB Output is correct
20 Correct 90 ms 22492 KB Output is correct
21 Correct 70 ms 20108 KB Output is correct
22 Correct 74 ms 20320 KB Output is correct
23 Correct 89 ms 19812 KB Output is correct
24 Correct 90 ms 20524 KB Output is correct
25 Correct 104 ms 25348 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8024 KB Output is correct
2 Correct 12 ms 8140 KB Output is correct
3 Correct 96 ms 20488 KB Output is correct
4 Correct 110 ms 21080 KB Output is correct
5 Correct 147 ms 22340 KB Output is correct
6 Correct 127 ms 22244 KB Output is correct
7 Correct 122 ms 22332 KB Output is correct
8 Correct 139 ms 22268 KB Output is correct
9 Runtime error 101 ms 33840 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8024 KB Output is correct
2 Correct 11 ms 8216 KB Output is correct
3 Partially correct 105 ms 20484 KB Output is partially correct
4 Correct 98 ms 20752 KB Output is correct
5 Partially correct 111 ms 21100 KB Output is partially correct
6 Partially correct 131 ms 22416 KB Output is partially correct
7 Correct 101 ms 20432 KB Output is correct
8 Partially correct 97 ms 20808 KB Output is partially correct
9 Partially correct 101 ms 21016 KB Output is partially correct
10 Partially correct 149 ms 22376 KB Output is partially correct
11 Partially correct 123 ms 22332 KB Output is partially correct
12 Partially correct 119 ms 22332 KB Output is partially correct
13 Partially correct 93 ms 18944 KB Output is partially correct
14 Runtime error 84 ms 35124 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -