제출 #435891

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

highway

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


using namespace std;
typedef long long ll;

vector<pair<int, int>> adj[90002];
vector<int> w;
int now, M;
int bfsorder[90002];
bool visited[90002];
int dist[90002][3];
ll D;
int K = -1, S = -1, T = -1;

void bfs(int x, int N, int t)
{
    for(int i=0;i<N;i++) visited[i] = false;
    visited[x] = true;
    queue<int> q;
    q.push(x);
    while(!q.empty())
    {
        int curr = q.front();
        q.pop();
        if(t == 2 && dist[curr][t] == D && dist[curr][1] == D - dist[S][1]) bfsorder[--now] = curr;
        else bfsorder[--now] = curr;

        for(auto u : adj[curr])
        {
            int i = u.first, j = u.second;
            if(!visited[i])
            {
                visited[i] = true;
                q.push(i);
                dist[i][t] = dist[curr][t] + 1;
            }
        }
    }
}

void makezero()
{
    for(int i=0;i<M;i++) w[i] = 0;
}

void binarysearch(int l, int r, ll zerotoll, int k)
{
    if(l == r)
    {
        if(k == 0) K = bfsorder[l];
        if(k == 1) S = bfsorder[l];
        if(k == 2) T = bfsorder[l];
        return;
    }
    int mid = (l + r)/2;
    makezero();
    for(int i=0;i<=mid;i++)
    {
        for(auto u : adj[bfsorder[i]])
        {
            w[u.second] = 1;
        }
    }
    ll toll = ask(w);

    if(toll > zerotoll) binarysearch(l, mid, zerotoll, k);
    else binarysearch(mid+1, r, zerotoll, k);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    M = U.size();
    for(int j=0;j<M;j++) { adj[U[j]].push_back({V[j], j}); adj[V[j]].push_back({U[j], j}); }
    w.resize(M);
    makezero();
    ll zerotoll = ask(w);

    D = zerotoll / A;

    now = N; bfs(0, N, 0);
    binarysearch(0, N-1, zerotoll, 0);
    now = N; bfs(K, N, 1);
    binarysearch(0, N-1, zerotoll, 1);
    if(dist[S][1] == D) { answer(K, S); return; }
    now = N; bfs(S, N, 2);
    binarysearch(0, N-1, zerotoll, 2);

    answer(S, T);
}

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

highway.cpp: In function 'void bfs(int, int, int)':
highway.cpp:32:30: warning: unused variable 'j' [-Wunused-variable]
   32 |             int i = u.first, j = u.second;
      |                              ^

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