Submission #435707

#	Time	Username	Problem	Language	Result	Execution time	Memory
435707		benedict0724	Highway Tolls (IOI18_highway)	C++17	0 / 100	18 ms	3144 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, v;
int now, M;
int bfsorder[90002];
bool visited[90002];
int dist[90002];
int U[90002];

int K = -1, S = -1, T = -1;
int cnt = 0;
ll D;

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

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

void makezero()
{
    for(int i=0;i<M;i++) w[i] = U[i];
}
void makeone()
{
    for(int i=0;i<M;i++) w[i] = 1;
}
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
    {
        for(int i=0;i<=mid;i++) U[i] = 1;
        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}); }
    for(int i=0;i<N;i++) v.push_back(i);
    random_shuffle(v.begin(), v.end());
    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, 0);
    binarysearch(now, N-1, zerotoll, 1);
    now = N; bfs(S, N, 1);
    binarysearch(0, cnt-1, zerotoll, 2);

    answer(S, T);
}

Compilation message (stderr)

highway.cpp: In function 'void bfs(int, int, int)':
highway.cpp:35:30: warning: unused variable 'j' [-Wunused-variable]
   35 |             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