oj.uz

Submission #952203

# Submission time Handle Problem Language Result Execution time Memory
952203 2024-03-23T09:34:02 Z Pikachu Highway Tolls (IOI18_highway) C++17
51 / 100
 142 ms 15512 KB 
#include <bits/stdc++.h>
#include "highway.h"
#define int long long

using namespace std;

const int maxn = 1e5 + 10;
int n, m;
int best;
vector<pair<int,int> > adj[maxn];
int d[2][maxn];
int dis[maxn];
int oe[maxn];
vector<pair<int,int> > edge[2];
int res[2];

void BFS(int u, int d[])
{
    queue<int> q;
    d[u] = 0;
    q.push(u);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (pair<int,int> p : adj[cur]) {
            if (d[p.first] == -1) {
                d[p.first] = d[cur] + 1;
                q.push(p.first);
            }
        }
    }
}

int findfirstedge()
{
    int l = 0;
    int r = m - 1;
    int ans = -1;
    best = ask(vector<signed>(m, 0));
    while (l <= r) {
        int mid = (l + r) >> 1;
        vector<signed> mim(m, 0);
        for (int i = 0; i <= mid; i++) mim[i] = 1;
        if (ask(mim) != best) {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    assert(ans != -1);
    return ans;
}

void find_pair(signed n, vector<signed> U, vector<signed> V, signed A, signed B) 
{
    ::n = n;
    m = U.size();
    for (int i = 0; i < m; i++) {
        adj[U[i]].push_back({V[i], i});
        adj[V[i]].push_back({U[i], i});
    }
    int e = findfirstedge();
    memset(d, -1, sizeof d);
    int u = U[e], v = V[e];
    BFS(u, d[0]);
    BFS(v, d[1]);
    // cout << u << ' ' << v << '\n';
    for (int i = 0; i < n; i++) {
        if (d[0][i] == d[1][i]) {
            oe[i] = -1;
            continue;
        }
        oe[i] = d[0][i] > d[1][i];
        dis[i] = min(d[0][i], d[1][i]);
        adj[i].clear();
    }
    for (int i = 0; i < m; i++) {
        signed &u = U[i], &v = V[i];
        if (oe[u] == -1 || oe[v] == -1) continue;
        if (oe[u] == oe[v]) {
            if (dis[u] == dis[v]) continue;
            if (dis[u] > dis[v]) swap(u, v);
            edge[oe[u]].push_back({dis[v], i});
        }
    }
    best = best / A * B;
    for (int id = 0; id < 2; id++) {
        sort(edge[id].begin(), edge[id].end());
        int l = 0;
        int r = edge[id].size() - 1;
        int ans = edge[id].size();
        while (l <= r) {
            int mid = (l + r) >> 1;
            vector<signed> mim(m, 1);
            for (int i = mid; i < (int)edge[id].size(); i++) {
                mim[edge[id][i].second] = 0;
            }
            if (ask(mim) != best) {
                l = mid + 1;
            }
            else {
                r = mid - 1;
                ans = mid;
            }
        }
        if (ans == 0) {
            res[id] = (id == 0 ? u : v);
        }
        else {
            res[id] = V[edge[id][ans - 1].second];
        }
    }
    // cout << best << '\n';
    // cout << res[0] << ' ' << res[1] << '\n';
    answer(res[0], res[1]);
}

#undef int

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5756 KB Output is correct
2 Correct 2 ms 5756 KB Output is correct
3 Correct 1 ms 5752 KB Output is correct
4 Correct 1 ms 5760 KB Output is correct
5 Correct 2 ms 5752 KB Output is correct
6 Correct 1 ms 5720 KB Output is correct
7 Correct 1 ms 5752 KB Output is correct
8 Correct 2 ms 5752 KB Output is correct
9 Correct 2 ms 5752 KB Output is correct
10 Correct 2 ms 5756 KB Output is correct
11 Correct 1 ms 5752 KB Output is correct
12 Correct 1 ms 5756 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5820 KB Output is correct
2 Correct 16 ms 6872 KB Output is correct
3 Correct 140 ms 14432 KB Output is correct
4 Correct 102 ms 14424 KB Output is correct
5 Correct 99 ms 14572 KB Output is correct
6 Correct 82 ms 14436 KB Output is correct
7 Correct 97 ms 14672 KB Output is correct
8 Correct 93 ms 14424 KB Output is correct
9 Correct 126 ms 14420 KB Output is correct
10 Correct 122 ms 14416 KB Output is correct
11 Correct 104 ms 14272 KB Output is correct
12 Correct 94 ms 14756 KB Output is correct
13 Correct 117 ms 14488 KB Output is correct
14 Correct 110 ms 15512 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6824 KB Output is correct
2 Correct 25 ms 7692 KB Output is correct
3 Correct 43 ms 8556 KB Output is correct
4 Correct 97 ms 13528 KB Output is correct
5 Correct 109 ms 13516 KB Output is correct
6 Correct 101 ms 14656 KB Output is correct
7 Correct 100 ms 14024 KB Output is correct
8 Correct 68 ms 13464 KB Output is correct
9 Correct 102 ms 14024 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5820 KB Output is correct
2 Correct 16 ms 6836 KB Output is correct
3 Correct 79 ms 12872 KB Output is correct
4 Correct 110 ms 14424 KB Output is correct
5 Correct 131 ms 14448 KB Output is correct
6 Correct 98 ms 14436 KB Output is correct
7 Correct 126 ms 14680 KB Output is correct
8 Correct 82 ms 14460 KB Output is correct
9 Correct 129 ms 14424 KB Output is correct
10 Correct 95 ms 14428 KB Output is correct
11 Correct 89 ms 14484 KB Output is correct
12 Correct 99 ms 14736 KB Output is correct
13 Correct 95 ms 14752 KB Output is correct
14 Correct 142 ms 14260 KB Output is correct
15 Correct 118 ms 14676 KB Output is correct
16 Correct 96 ms 14504 KB Output is correct
17 Correct 97 ms 14480 KB Output is correct
18 Correct 106 ms 14580 KB Output is correct
19 Correct 93 ms 14936 KB Output is correct
20 Correct 115 ms 14492 KB Output is correct
21 Correct 71 ms 15124 KB Output is correct
22 Correct 80 ms 15356 KB Output is correct
23 Correct 101 ms 14316 KB Output is correct
24 Correct 93 ms 14304 KB Output is correct
25 Correct 136 ms 14460 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 6792 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 6712 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -