제출 #279931

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
279931		hamerin	통행료 (IOI18_highway)	C++17	100 / 100	337 ms	12104 KiB

highway

#include "highway.h"

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

void find_pair(const int N, vector<int> U, vector<int> V, int A, int B) {
    const int M = U.size();

    i64 defaultDist = ask(vector<int>(M));
    int dst = defaultDist / A;

    int edgUsed;
    {
        int s = 0, e = M - 1;
        while (s < e) {
            int m = (s + e + 1) >> 1;

            vector<int> q(M);
            fill(q.begin(), q.begin() + m, 1);

            i64 d = ask(q);

            if (d == defaultDist)
                s = m;
            else
                e = m - 1;
        }

        edgUsed = s;
    }

    int u = U[edgUsed];
    int v = V[edgUsed];

    vector<vector<pi>> graph(N);
    for (int i = 0; i < M; i++) {
        graph[U[i]].emplace_back(V[i], i);
        graph[V[i]].emplace_back(U[i], i);
    }

    vector<int> vtyp(N), par(N);
    vector<i64> distu(N, -1), distv(N, -1);

    distu[u] = distv[v] = 0;

    {
        queue<int> que;
        que.emplace(u);

        while (!que.empty()) {
            auto cur = que.front();
            que.pop();

            for (auto [t, _] : graph[cur]) {
                if (distu[t] == -1) {
                    distu[t] = distu[cur] + 1;
                    par[t] = cur;
                    que.emplace(t);
                }
            }
        }
    }

    {
        queue<int> que;
        que.emplace(v);

        while (!que.empty()) {
            auto cur = que.front();
            que.pop();

            for (auto [t, _] : graph[cur]) {
                if (distv[t] == -1) {
                    distv[t] = distv[cur] + 1;
                    par[t] = cur;
                    que.emplace(t);
                }
            }
        }
    }

    int us, vs;

    for (int i = 0; i < N; i++) {
        if (distv[i] > distu[i]) vtyp[i] = 1;
        if (distu[i] > distv[i]) vtyp[i] = 2;
    }

    {
        vector<int> hb;
        for (int i = 0; i < N; i++)
            if (vtyp[i] == 1) hb.emplace_back(i);

        auto H = hb.size();

        sort(iterall(hb), [&](int l, int r) {
            return distu[l] < distu[r];
        });

        int s = 0, e = H - 1;
        while (s < e) {
            int m = (s + e + 1) >> 1;

            vector<int> q(M);
            vector<bool> c(N);
            for (int i = m; i < H; i++) c[hb[i]] = true;
            for (int i = 0; i < M; i++)
                if (c[U[i]] || c[V[i]]) q[i] = 1;

            i64 d = ask(q);
            if (d == defaultDist)
                e = m - 1;
            else
                s = m;
        }

        us = hb[s];
    }

    {
        vector<int> hb;
        for (int i = 0; i < N; i++)
            if (vtyp[i] == 2) hb.emplace_back(i);

        auto H = hb.size();

        sort(iterall(hb), [&](int l, int r) {
            return distv[l] < distv[r];
        });

        int s = 0, e = H - 1;
        while (s < e) {
            int m = (s + e + 1) >> 1;

            vector<int> q(M);
            vector<bool> c(N);
            for (int i = m; i < H; i++) c[hb[i]] = true;
            for (int i = 0; i < M; i++)
                if (c[U[i]] || c[V[i]]) q[i] = 1;

            i64 d = ask(q);
            if (d == defaultDist)
                e = m - 1;
            else
                s = m;
        }

        vs = hb[s];
    }

    answer(us, vs);
}

컴파일 시 표준 에러 (stderr) 메시지

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:120:31: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
  120 |             for (int i = m; i < H; i++) c[hb[i]] = true;
      |                             ~~^~~
highway.cpp:151:31: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
  151 |             for (int i = m; i < H; i++) c[hb[i]] = true;
      |                             ~~^~~
highway.cpp:24:9: warning: unused variable 'dst' [-Wunused-variable]
   24 |     int dst = defaultDist / A;
      |         ^~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 18 / 18
• Subtask 6: 31 / 31