oj.uz

Submission #952034

# Submission time Handle Problem Language Result Execution time Memory
952034 2024-03-23T03:59:42 Z Pikachu Highway Tolls (IOI18_highway) C++17
51 / 100
 165 ms 17652 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;
    }
    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]);
    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});
        }
    }
    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, 0);
            for (int i = mid; i < (int)edge[id].size(); i++) {
                mim[edge[id][i].second] = 1;
            }
            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];
        }
    }
    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 2 ms 5756 KB Output is correct
3 Correct 2 ms 5756 KB Output is correct
4 Correct 2 ms 5756 KB Output is correct
5 Correct 2 ms 5756 KB Output is correct
6 Correct 1 ms 5752 KB Output is correct
7 Correct 1 ms 5752 KB Output is correct
8 Correct 1 ms 5752 KB Output is correct
9 Correct 2 ms 5756 KB Output is correct
10 Correct 2 ms 5760 KB Output is correct
11 Correct 2 ms 5748 KB Output is correct
12 Correct 2 ms 5756 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5824 KB Output is correct
2 Correct 10 ms 6712 KB Output is correct
3 Correct 89 ms 14420 KB Output is correct
4 Correct 146 ms 14448 KB Output is correct
5 Correct 137 ms 14432 KB Output is correct
6 Correct 111 ms 14416 KB Output is correct
7 Correct 134 ms 14444 KB Output is correct
8 Correct 112 ms 14424 KB Output is correct
9 Correct 88 ms 14412 KB Output is correct
10 Correct 109 ms 14688 KB Output is correct
11 Correct 114 ms 14736 KB Output is correct
12 Correct 125 ms 14744 KB Output is correct
13 Correct 103 ms 14484 KB Output is correct
14 Correct 96 ms 14488 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 19 ms 7704 KB Output is correct
3 Correct 28 ms 8504 KB Output is correct
4 Correct 70 ms 13820 KB Output is correct
5 Correct 75 ms 13608 KB Output is correct
6 Correct 88 ms 14288 KB Output is correct
7 Correct 74 ms 14024 KB Output is correct
8 Correct 72 ms 13708 KB Output is correct
9 Correct 74 ms 14136 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 12 ms 6996 KB Output is correct
3 Correct 79 ms 12660 KB Output is correct
4 Correct 83 ms 14436 KB Output is correct
5 Correct 117 ms 14420 KB Output is correct
6 Correct 100 ms 14424 KB Output is correct
7 Correct 85 ms 14432 KB Output is correct
8 Correct 92 ms 14668 KB Output is correct
9 Correct 109 ms 14688 KB Output is correct
10 Correct 118 ms 14428 KB Output is correct
11 Correct 105 ms 14636 KB Output is correct
12 Correct 118 ms 14484 KB Output is correct
13 Correct 119 ms 14744 KB Output is correct
14 Correct 118 ms 14264 KB Output is correct
15 Correct 90 ms 14672 KB Output is correct
16 Correct 108 ms 14424 KB Output is correct
17 Correct 120 ms 14484 KB Output is correct
18 Correct 147 ms 14484 KB Output is correct
19 Correct 98 ms 14476 KB Output is correct
20 Correct 113 ms 14500 KB Output is correct
21 Correct 92 ms 15116 KB Output is correct
22 Correct 77 ms 15360 KB Output is correct
23 Correct 105 ms 14540 KB Output is correct
24 Correct 81 ms 14796 KB Output is correct
25 Correct 105 ms 14464 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6780 KB Output is correct
2 Correct 18 ms 6856 KB Output is correct
3 Correct 110 ms 15156 KB Output is correct
4 Correct 127 ms 15652 KB Output is correct
5 Correct 160 ms 17060 KB Output is correct
6 Correct 165 ms 17324 KB Output is correct
7 Correct 130 ms 17652 KB Output is correct
8 Incorrect 135 ms 17292 KB Output is incorrect: {s, t} is wrong.
9 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6844 KB Output is correct
2 Correct 15 ms 6852 KB Output is correct
3 Correct 114 ms 15192 KB Output is correct
4 Correct 135 ms 15432 KB Output is correct
5 Correct 162 ms 15872 KB Output is correct
6 Correct 162 ms 17272 KB Output is correct
7 Correct 110 ms 15208 KB Output is correct
8 Correct 153 ms 15504 KB Output is correct
9 Incorrect 146 ms 16260 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -