oj.uz

Submission #952207

# Submission time Handle Problem Language Result Execution time Memory
952207 2024-03-23T09:39:17 Z Pikachu Highway Tolls (IOI18_highway) C++17
51 / 100
 141 ms 15400 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));
    vector<int> id(m);
    iota(id.begin(), id.end(), 0);
    random_shuffle(id.begin(), id.end());
    while (l <= r) {
        int mid = (l + r) >> 1;
        vector<signed> mim(m, 0);
        for (int i = 0; i <= mid; i++) mim[id[i]] = 1;
        if (ask(mim) != best) {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    assert(ans != -1);
    return id[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 5752 KB Output is correct
2 Correct 1 ms 5756 KB Output is correct
3 Correct 1 ms 5752 KB Output is correct
4 Correct 2 ms 5752 KB Output is correct
5 Correct 2 ms 5752 KB Output is correct
6 Correct 2 ms 5748 KB Output is correct
7 Correct 1 ms 5752 KB Output is correct
8 Correct 1 ms 5760 KB Output is correct
9 Correct 2 ms 5756 KB Output is correct
10 Correct 1 ms 5756 KB Output is correct
11 Correct 2 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 5816 KB Output is correct
2 Correct 12 ms 6796 KB Output is correct
3 Correct 104 ms 14940 KB Output is correct
4 Correct 97 ms 14940 KB Output is correct
5 Correct 134 ms 14936 KB Output is correct
6 Correct 110 ms 14940 KB Output is correct
7 Correct 106 ms 14940 KB Output is correct
8 Correct 95 ms 15400 KB Output is correct
9 Correct 92 ms 15148 KB Output is correct
10 Correct 95 ms 15188 KB Output is correct
11 Correct 101 ms 14492 KB Output is correct
12 Correct 94 ms 15004 KB Output is correct
13 Correct 123 ms 14996 KB Output is correct
14 Correct 99 ms 14240 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7004 KB Output is correct
2 Correct 28 ms 7852 KB Output is correct
3 Correct 40 ms 8548 KB Output is correct
4 Correct 86 ms 13988 KB Output is correct
5 Correct 69 ms 13992 KB Output is correct
6 Correct 117 ms 13984 KB Output is correct
7 Correct 66 ms 14548 KB Output is correct
8 Correct 74 ms 14428 KB Output is correct
9 Correct 95 ms 14548 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 13 ms 6916 KB Output is correct
3 Correct 79 ms 12904 KB Output is correct
4 Correct 100 ms 14868 KB Output is correct
5 Correct 122 ms 14948 KB Output is correct
6 Correct 141 ms 14940 KB Output is correct
7 Correct 102 ms 14944 KB Output is correct
8 Correct 107 ms 14936 KB Output is correct
9 Correct 128 ms 14964 KB Output is correct
10 Correct 101 ms 15148 KB Output is correct
11 Correct 115 ms 15000 KB Output is correct
12 Correct 133 ms 14240 KB Output is correct
13 Correct 115 ms 14216 KB Output is correct
14 Correct 102 ms 14492 KB Output is correct
15 Correct 102 ms 14940 KB Output is correct
16 Correct 114 ms 15184 KB Output is correct
17 Correct 113 ms 14488 KB Output is correct
18 Correct 94 ms 15024 KB Output is correct
19 Correct 111 ms 15188 KB Output is correct
20 Correct 141 ms 15228 KB Output is correct
21 Correct 80 ms 15172 KB Output is correct
22 Correct 117 ms 15128 KB Output is correct
23 Correct 100 ms 14292 KB Output is correct
24 Correct 99 ms 14560 KB Output is correct
25 Correct 138 ms 15184 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 7024 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 14 ms 7020 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -