oj.uz

답안 #952206

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
952206 2024-03-23T09:38:56 Z Pikachu 통행료 (IOI18_highway) C++17
0 / 100
 14 ms 7024 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 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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 5756 KB Output is correct
2 Incorrect 1 ms 5756 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 5820 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 6904 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 5816 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 6968 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 7024 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -