oj.uz

Submission #1055618

# Submission time Handle Problem Language Result Execution time Memory
1055618 2024-08-13T00:22:43 Z efishel Highway Tolls (IOI18_highway) C++17
0 / 100
 9 ms 5208 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];
bool vis[MAXN];
ll toPar[MAXN];

vll ord;
void dfs (ll u) {
    vis[u] = true;
    for (auto [v, id] : adj[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))/a;
    // {ll l = 0, r = n;
    // while (l+1 < r) {
    //     ll mid = (l+r)>>1;
    //     vi vask(m);
    //     for (ll i = 0; i < m; i++) vask[i] = i < mid;
    //     if (ask(vask) == dis) {
    //         ;
    //     }
    // }}
    // todo: make tree
    vi askMask(m, 0);
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3416 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3672 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5208 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3672 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 4728 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 4696 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
2 Halted 0 ms 0 KB -