oj.uz

Submission #1057209

# Submission time Handle Problem Language Result Execution time Memory
1057209 2024-08-13T15:18:49 Z efishel Highway Tolls (IOI18_highway) C++17
5 / 100
 135 ms 37076 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] || askMask[id] == 1) 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 2 ms 7512 KB Output is correct
2 Correct 1 ms 7512 KB Output is correct
3 Correct 1 ms 7512 KB Output is correct
4 Correct 1 ms 7512 KB Output is correct
5 Correct 2 ms 7512 KB Output is correct
6 Correct 1 ms 7512 KB Output is correct
7 Correct 2 ms 7512 KB Output is correct
8 Correct 1 ms 7512 KB Output is correct
9 Correct 2 ms 7512 KB Output is correct
10 Correct 1 ms 7512 KB Output is correct
11 Correct 1 ms 7352 KB Output is correct
12 Correct 2 ms 7512 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 9 ms 8792 KB Output is correct
3 Correct 100 ms 19160 KB Output is correct
4 Correct 86 ms 19120 KB Output is correct
5 Correct 88 ms 20140 KB Output is correct
6 Correct 96 ms 17404 KB Output is correct
7 Correct 69 ms 16956 KB Output is correct
8 Correct 87 ms 20136 KB Output is correct
9 Correct 88 ms 17108 KB Output is correct
10 Runtime error 72 ms 37076 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 16984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 8 ms 8536 KB Output is correct
3 Correct 61 ms 17396 KB Output is correct
4 Correct 75 ms 18848 KB Output is correct
5 Runtime error 62 ms 29056 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8864 KB Output is correct
2 Runtime error 14 ms 17496 KB Execution killed with signal 11
3 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 11 ms 9048 KB Output is correct
3 Partially correct 99 ms 20704 KB Output is partially correct
4 Correct 98 ms 20952 KB Output is correct
5 Partially correct 119 ms 20992 KB Output is partially correct
6 Partially correct 113 ms 22364 KB Output is partially correct
7 Correct 111 ms 20684 KB Output is correct
8 Partially correct 98 ms 21240 KB Output is partially correct
9 Partially correct 110 ms 20872 KB Output is partially correct
10 Correct 135 ms 22528 KB Output is correct
11 Partially correct 122 ms 22580 KB Output is partially correct
12 Partially correct 133 ms 22512 KB Output is partially correct
13 Runtime error 105 ms 32960 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -