oj.uz

Submission #952020

# Submission time Handle Problem Language Result Execution time Memory
952020 2024-03-23T03:48:41 Z Pikachu Highway Tolls (IOI18_highway) C++17
5 / 100
 166 ms 13192 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++) {
        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] == 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 4188 KB Output is correct
2 Correct 1 ms 4188 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 1 ms 4188 KB Output is correct
5 Correct 1 ms 4180 KB Output is correct
6 Correct 1 ms 4192 KB Output is correct
7 Correct 1 ms 4192 KB Output is correct
8 Correct 2 ms 4176 KB Output is correct
9 Correct 2 ms 4192 KB Output is correct
10 Correct 2 ms 4188 KB Output is correct
11 Correct 2 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 4 ms 4240 KB Output is correct
2 Correct 12 ms 5156 KB Output is correct
3 Correct 119 ms 10588 KB Output is correct
4 Correct 91 ms 10804 KB Output is correct
5 Correct 120 ms 10588 KB Output is correct
6 Correct 95 ms 10812 KB Output is correct
7 Correct 136 ms 10596 KB Output is correct
8 Correct 96 ms 10656 KB Output is correct
9 Correct 94 ms 10780 KB Output is correct
10 Correct 98 ms 10836 KB Output is correct
11 Correct 126 ms 10320 KB Output is correct
12 Correct 120 ms 10464 KB Output is correct
13 Correct 94 ms 10040 KB Output is correct
14 Incorrect 96 ms 10036 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 10 ms 4692 KB Output is correct
2 Correct 29 ms 5496 KB Output is correct
3 Correct 33 ms 6164 KB Output is correct
4 Correct 74 ms 10032 KB Output is correct
5 Correct 113 ms 10020 KB Output is correct
6 Correct 94 ms 10136 KB Output is correct
7 Correct 68 ms 10032 KB Output is correct
8 Correct 72 ms 10132 KB Output is correct
9 Incorrect 87 ms 10032 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 12 ms 4960 KB Output is correct
3 Correct 90 ms 9072 KB Output is correct
4 Correct 105 ms 10576 KB Output is correct
5 Correct 87 ms 10580 KB Output is correct
6 Correct 92 ms 10580 KB Output is correct
7 Correct 104 ms 10604 KB Output is correct
8 Correct 116 ms 10576 KB Output is correct
9 Incorrect 129 ms 10588 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 4972 KB Output is correct
2 Correct 13 ms 5000 KB Output is correct
3 Correct 115 ms 10940 KB Output is correct
4 Correct 121 ms 11720 KB Output is correct
5 Correct 147 ms 12496 KB Output is correct
6 Correct 142 ms 12632 KB Output is correct
7 Correct 166 ms 12628 KB Output is correct
8 Incorrect 146 ms 13192 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 12 ms 5144 KB Output is correct
2 Correct 20 ms 5004 KB Output is correct
3 Correct 140 ms 11600 KB Output is correct
4 Correct 115 ms 11624 KB Output is correct
5 Correct 119 ms 11676 KB Output is correct
6 Correct 145 ms 12936 KB Output is correct
7 Correct 138 ms 10980 KB Output is correct
8 Correct 118 ms 11616 KB Output is correct
9 Incorrect 122 ms 11652 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -