제출 #1207761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1207761		omsincoconut	통행료 (IOI18_highway)	C++17	90 / 100	155 ms	10408 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<int> bfs_order(int N, int M, int source, vector<int> U, vector<int> V) {
    vector<int> edge[N];
    for (int i = 0; i < M; i++) {
        edge[U[i]].push_back(V[i]);
        edge[V[i]].push_back(U[i]);
    }

    int cur = 0;
    vector<int> ret(N, -1);
    queue<int> bfs;
    bfs.push(source);
    while (!bfs.empty()) {
        int u = bfs.front();
        bfs.pop();
        if (ret[u] > -1) continue;
        ret[u] = cur++;

        for (int v : edge[u])
            bfs.push(v);
    }

    return ret;
}

int find_first(int N, int M, int source, ll targ, vector<int> U, vector<int> V) {
    vector<int> ord = bfs_order(N, M, source, U, V);
    int l = -1, r = N-1;
    while (r-l > 1) {
        int mid = (l+r)>>1;

        vector<int> query(M, 1);
        for (int i = 0; i < M; i++)
            if (ord[U[i]] <= mid && ord[V[i]] <= mid)
                query[i] = 0;

        if (ask(query) > targ) l = mid;
        else r = mid;
    }

    for (int i = 0; i < N; i++)
        if (ord[i] == r)
            return i;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    int M = U.size();
    ll shortest_path = ask(vector<int>(M, 0));
    
    // Find one node on the shortest path from S to T
    int midnode = -1;
    {
        int l = -1, r = N-1;
        while (r-l > 1) {
            int mid = (l+r)>>1;
            vector<int> query(M, 0);
            for (int i = 0; i < M; i++)
                if (U[i] <= mid || V[i] <= mid)
                    query[i] = 1;
            if (ask(query) > shortest_path) r = mid;
            else l = mid;
        }
        midnode = r;
    }

    int S = find_first(N, M, midnode, shortest_path, U, V);
    int T = find_first(N, M, S, shortest_path, U, V);

    answer(S, T);
}

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

highway.cpp: In function 'int find_first(int, int, int, ll, std::vector<int>, std::vector<int>)':
highway.cpp:49:1: warning: control reaches end of non-void function [-Wreturn-type]
   49 | }
      | ^

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