oj.uz

Submission #1057602

# Submission time Handle Problem Language Result Execution time Memory
1057602 2024-08-13T23:31:46 Z efishel Highway Tolls (IOI18_highway) C++17
90 / 100
 506 ms 27720 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];
ll dep[MAXN];

vll ord;
void dfs (ll u) {
    vis[u] = true;
    for (auto [v, id] : adjT[u]) {
        if (vis[v]) continue;
        dep[v] = dep[u]+1;
        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, -15);
    ll src1 = -15, src2 = -15;
    {ll l = -1, r = m-1;
    while (l+1 < r) {
        ll mid = (l+r)>>1;
        vi vask(m, 0);
        for (ll i = 0; i <= mid; i++) vask[i] = 1;
        if (ask(vask) == dis)
            l = mid;
        else
            r = mid;
    }
    askMask = vi(m, 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 });
    askMask[r] = 0;
    while (q.size()) {
        ll u = q.front(); q.pop();
        for (auto [v, id] : adj[u]) {
            if (vis[v] || id <= l) continue;
            vis[v] = true; q.push(v);
            cerr << u << ' ' << v << '\n';
            adjT[u].push_back({ v, id });
            adjT[v].push_back({ u, id });
            askMask[id] = 0;
        }
    }}
    dep[src1] = 0;
    dfs(src1);
    // for (ll i : askMask) cout << i << ' ';
    // cout << " askMask\n";
    // for (ll i : ord) cout << i << ' ';
    // cout << " ord\n";
    // for (ll i : ord) cout << toPar[i] << ' ';
    // cout << " par[ord]\n";
    ll u1 = -15, u2 = -15;
    {ll l = -1, r = ord.size();
    // l es normal
    // r lo corta
    while (l+1 < r) {
        ll mid = (l+r)>>1;
        vi vask(askMask.begin(), askMask.end());
        for (ll i = 0; i <= mid; i++) vask[toPar[ord[i]]] = 1;
        if (ask(vask) == dis)
            l = mid;
        else
            r = mid;
    }
    u1 = ord[r];}
    // cout << u1 << " u1\n";
    fill(vis, vis+MAXN, false);
    ord.clear();
    dep[u1] = 0;
    dfs(u1);
    // for (ll i : ord) cout << i << ' ';
    // cout << " ord\n";
    {ll l = -1, r = ord.size();
    // l es normal
    // r lo corta
    while (l+1 < r) {
        ll mid = (l+r)>>1;
        vi vask(askMask.begin(), askMask.end());
        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 8532 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 2 ms 8536 KB Output is correct
4 Correct 2 ms 8536 KB Output is correct
5 Correct 1 ms 8536 KB Output is correct
6 Correct 2 ms 8536 KB Output is correct
7 Correct 2 ms 8536 KB Output is correct
8 Correct 2 ms 8308 KB Output is correct
9 Correct 2 ms 8536 KB Output is correct
10 Correct 2 ms 8536 KB Output is correct
11 Correct 2 ms 8536 KB Output is correct
12 Correct 2 ms 8536 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8536 KB Output is correct
2 Correct 62 ms 10068 KB Output is correct
3 Correct 333 ms 21072 KB Output is correct
4 Correct 304 ms 20884 KB Output is correct
5 Correct 377 ms 22128 KB Output is correct
6 Correct 242 ms 18980 KB Output is correct
7 Correct 202 ms 18440 KB Output is correct
8 Correct 377 ms 22176 KB Output is correct
9 Correct 269 ms 18624 KB Output is correct
10 Correct 292 ms 20236 KB Output is correct
11 Correct 100 ms 16900 KB Output is correct
12 Correct 381 ms 23712 KB Output is correct
13 Correct 375 ms 23340 KB Output is correct
14 Correct 419 ms 23672 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 10580 KB Output is correct
2 Correct 67 ms 12384 KB Output is correct
3 Correct 35 ms 11036 KB Output is correct
4 Correct 244 ms 23116 KB Output is correct
5 Correct 250 ms 23248 KB Output is correct
6 Correct 305 ms 25824 KB Output is correct
7 Correct 67 ms 15700 KB Output is correct
8 Correct 322 ms 24268 KB Output is correct
9 Correct 146 ms 18512 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8536 KB Output is correct
2 Correct 33 ms 9816 KB Output is correct
3 Correct 293 ms 19236 KB Output is correct
4 Correct 333 ms 20652 KB Output is correct
5 Correct 63 ms 15944 KB Output is correct
6 Correct 56 ms 15780 KB Output is correct
7 Correct 195 ms 18464 KB Output is correct
8 Correct 86 ms 16064 KB Output is correct
9 Correct 338 ms 21248 KB Output is correct
10 Correct 258 ms 19500 KB Output is correct
11 Correct 383 ms 23012 KB Output is correct
12 Correct 366 ms 23256 KB Output is correct
13 Correct 297 ms 21688 KB Output is correct
14 Correct 148 ms 18388 KB Output is correct
15 Correct 71 ms 15824 KB Output is correct
16 Correct 58 ms 15632 KB Output is correct
17 Correct 356 ms 22500 KB Output is correct
18 Correct 388 ms 23972 KB Output is correct
19 Correct 76 ms 15764 KB Output is correct
20 Correct 75 ms 16012 KB Output is correct
21 Correct 244 ms 19296 KB Output is correct
22 Correct 151 ms 17096 KB Output is correct
23 Correct 376 ms 22204 KB Output is correct
24 Correct 435 ms 22920 KB Output is correct
25 Correct 399 ms 27720 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 10064 KB Output is correct
2 Correct 39 ms 9940 KB Output is correct
3 Correct 402 ms 22840 KB Output is correct
4 Correct 359 ms 22508 KB Output is correct
5 Correct 385 ms 23744 KB Output is correct
6 Correct 452 ms 24724 KB Output is correct
7 Correct 403 ms 24344 KB Output is correct
8 Correct 413 ms 24108 KB Output is correct
9 Correct 85 ms 17172 KB Output is correct
10 Correct 162 ms 19508 KB Output is correct
11 Correct 217 ms 20452 KB Output is correct
12 Correct 353 ms 23360 KB Output is correct
13 Correct 387 ms 23896 KB Output is correct
14 Correct 493 ms 24732 KB Output is correct
15 Correct 419 ms 24732 KB Output is correct
16 Correct 234 ms 20816 KB Output is correct
17 Correct 293 ms 19740 KB Output is correct
18 Correct 106 ms 16640 KB Output is correct
19 Correct 318 ms 21724 KB Output is correct
20 Correct 176 ms 18204 KB Output is correct
21 Correct 416 ms 25144 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 10064 KB Output is correct
2 Correct 42 ms 10064 KB Output is correct
3 Correct 423 ms 22740 KB Output is correct
4 Correct 420 ms 22804 KB Output is correct
5 Partially correct 404 ms 23124 KB Output is partially correct
6 Partially correct 417 ms 24444 KB Output is partially correct
7 Correct 389 ms 22748 KB Output is correct
8 Correct 400 ms 23000 KB Output is correct
9 Partially correct 397 ms 23012 KB Output is partially correct
10 Partially correct 417 ms 24736 KB Output is partially correct
11 Partially correct 415 ms 24636 KB Output is partially correct
12 Correct 402 ms 24348 KB Output is correct
13 Correct 99 ms 18360 KB Output is correct
14 Correct 78 ms 18460 KB Output is correct
15 Correct 231 ms 21144 KB Output is correct
16 Correct 171 ms 19512 KB Output is correct
17 Correct 214 ms 20424 KB Output is correct
18 Correct 171 ms 19796 KB Output is correct
19 Correct 369 ms 23432 KB Output is correct
20 Partially correct 444 ms 23988 KB Output is partially correct
21 Correct 471 ms 24748 KB Output is correct
22 Correct 432 ms 24748 KB Output is correct
23 Correct 456 ms 24732 KB Output is correct
24 Partially correct 435 ms 24748 KB Output is partially correct
25 Partially correct 414 ms 24468 KB Output is partially correct
26 Correct 431 ms 24692 KB Output is correct
27 Correct 193 ms 18352 KB Output is correct
28 Correct 300 ms 20896 KB Output is correct
29 Correct 364 ms 23180 KB Output is correct
30 Correct 369 ms 22232 KB Output is correct
31 Correct 315 ms 21164 KB Output is correct
32 Correct 322 ms 21472 KB Output is correct
33 Partially correct 372 ms 22892 KB Output is partially correct
34 Correct 269 ms 20056 KB Output is correct
35 Correct 285 ms 20452 KB Output is correct
36 Partially correct 378 ms 21724 KB Output is partially correct
37 Correct 295 ms 21484 KB Output is correct
38 Correct 345 ms 22076 KB Output is correct
39 Partially correct 506 ms 25800 KB Output is partially correct
40 Partially correct 419 ms 25688 KB Output is partially correct
41 Partially correct 491 ms 25136 KB Output is partially correct
42 Partially correct 421 ms 25076 KB Output is partially correct