oj.uz

Submission #952023

# Submission time Handle Problem Language Result Execution time Memory
952023 2024-03-23T03:50:57 Z Pikachu Highway Tolls (IOI18_highway) C++17
5 / 100
 167 ms 12728 KB 
#include <bits/stdc++.h>
#include "highway.h"

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<int>(m, 0));
    while (l <= r) {
        int mid = (l + r) >> 1;
        vector<int> 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(int n, vector<int> U, vector<int> V, int A, int 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++) {
        int &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<int> 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]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4192 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 1 ms 4180 KB Output is correct
4 Correct 2 ms 4184 KB Output is correct
5 Correct 2 ms 4184 KB Output is correct
6 Correct 1 ms 4192 KB Output is correct
7 Correct 1 ms 4188 KB Output is correct
8 Correct 1 ms 4184 KB Output is correct
9 Correct 2 ms 4192 KB Output is correct
10 Correct 1 ms 4192 KB Output is correct
11 Correct 1 ms 4188 KB Output is correct
12 Correct 2 ms 4184 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4240 KB Output is correct
2 Correct 15 ms 4968 KB Output is correct
3 Correct 112 ms 10880 KB Output is correct
4 Correct 95 ms 10584 KB Output is correct
5 Correct 94 ms 10636 KB Output is correct
6 Correct 110 ms 10588 KB Output is correct
7 Correct 98 ms 10844 KB Output is correct
8 Correct 96 ms 10580 KB Output is correct
9 Correct 88 ms 10748 KB Output is correct
10 Correct 84 ms 10584 KB Output is correct
11 Correct 91 ms 10096 KB Output is correct
12 Correct 123 ms 10492 KB Output is correct
13 Correct 98 ms 10032 KB Output is correct
14 Incorrect 111 ms 10048 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4876 KB Output is correct
2 Correct 24 ms 5492 KB Output is correct
3 Correct 23 ms 6168 KB Output is correct
4 Correct 83 ms 10036 KB Output is correct
5 Correct 84 ms 10064 KB Output is correct
6 Correct 80 ms 10400 KB Output is correct
7 Correct 70 ms 10260 KB Output is correct
8 Correct 92 ms 10384 KB Output is correct
9 Incorrect 69 ms 10036 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4240 KB Output is correct
2 Correct 17 ms 4952 KB Output is correct
3 Correct 97 ms 9444 KB Output is correct
4 Correct 109 ms 10832 KB Output is correct
5 Correct 89 ms 10832 KB Output is correct
6 Correct 100 ms 10596 KB Output is correct
7 Correct 102 ms 11032 KB Output is correct
8 Correct 94 ms 10588 KB Output is correct
9 Incorrect 89 ms 10592 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5136 KB Output is correct
2 Correct 19 ms 5000 KB Output is correct
3 Correct 109 ms 10932 KB Output is correct
4 Correct 128 ms 11552 KB Output is correct
5 Correct 167 ms 12368 KB Output is correct
6 Correct 142 ms 12728 KB Output is correct
7 Correct 148 ms 12640 KB Output is correct
8 Incorrect 135 ms 12160 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 13 ms 5200 KB Output is correct
2 Correct 13 ms 5000 KB Output is correct
3 Correct 129 ms 10812 KB Output is correct
4 Correct 111 ms 11268 KB Output is correct
5 Correct 159 ms 11524 KB Output is correct
6 Correct 132 ms 12328 KB Output is correct
7 Correct 96 ms 10964 KB Output is correct
8 Correct 105 ms 11136 KB Output is correct
9 Incorrect 144 ms 11524 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -