Submission #435523

#	Time	Username	Problem	Language	Result	Execution time	Memory
435523		benedict0724	Highway Tolls (IOI18_highway)	C++17	0 / 100	678 ms	15980 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 A = -1, S = -1, T = -1;

void bfs(int x, int N)
{
    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();
        bfsorder[--now] = curr;

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

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) A = 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);

    now = N; bfs(0, N);
    binarysearch(0, N-1, zerotoll, 0);
    now = N; bfs(A, N);
    binarysearch(0, N-1, zerotoll, 1);
    now = N; bfs(S, N);
    binarysearch(0, N-2, zerotoll, 2);

    answer(S, T);
}

Compilation message (stderr)

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

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