Submission #1170198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170198		ZeroCool	Highway Tolls (IOI18_highway)	C++20	100 / 100	107 ms	16216 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

#define all(v) v.begin(), v.end()
#define ar array

#define int long long

void find_pair(signed n, std::vector<signed> u, std::vector<signed> v, signed a, signed b) {
    vector<ar<int, 2>> g[n];
    int m = u.size();
    for(int i= 0;i < m;i++){
        g[u[i]].push_back({v[i], i});
        g[v[i]].push_back({u[i], i});
    }
    vector<signed> Q(m, 0);
    int w = ask(Q);
    ar<int, 2> e;
    int ee;
    {
        int lo = -1, hi = m;
        while(hi - lo >1){
            int mid = (lo + hi) / 2;
            for(int i = 0;i < m;i++)Q[i] = i <= mid;
            if(ask(Q) != w)hi = mid;
            else lo = mid;
        }
        ee = hi;
        e = {u[hi], v[hi]};
    };
    int dst[n][2];
    memset(dst, -1, sizeof dst);
    for(int j = 0;j < 2;j++){
        queue<int> q;
        dst[e[j]][j] = 0;
        q.push(e[j]);
        while(q.size()){
            int x = q.front();
            q.pop();
            for(auto [u, i]: g[x]){
                if(dst[u][j] == -1){
                    dst[u][j] = dst[x][j] + 1;
                    q.push(u);
                }
            }
        }
    }
    ar<int, 2> ans;
    for(int j = 0;j < 2;j++){
        int t = 0;
        int A[m];
        int V[m];
        int d[n];
        memset(d, -1, sizeof d);
        memset(A, -1, sizeof A);
        memset(V, -1, sizeof V);
        d[e[j]] = 0;
        queue<int> q;
        q.push(e[j]);
        while(q.size()){
            int x = q.front();
            q.pop();
            for(auto [u, i]: g[x]){
                if(dst[u][j] < dst[u][j ^ 1]){
                    if(d[u] == -1){
                        d[u] = d[x] +1 ;
                        q.push(u);
                        V[t] = u;
                        A[i] = t++;
                    }else if(d[u] == d[x] + 1)A[i] = n;
                }else if(i != ee)A[i] = n;
            }
        }
       // cout<<e[j]<<": ";
        //for(int i = 0;i < m;i++)cout<<A[i]<<" ";
        //cout<<'\n';
        int lo = -1, hi = t;
        while(hi - lo > 1){
            int mid = (lo + hi) / 2;
            for(int i = 0;i < m;i++)Q[i] = A[i] >= mid;
            if(ask(Q) != w)lo = mid;
            else hi = mid;
        }
        if(lo == -1)ans[j] = e[j];
        else ans[j] = V[lo];
    }
   // cout<<ans[0]<<" "<<ans[1]<<endl;
    answer(ans[0], ans[1]);
}

#define int signed

Compilation message (stderr)

highway.cpp:92: warning: "int" redefined
   92 | #define int signed
      | 
highway.cpp:8: note: this is the location of the previous definition
    8 | #define int long long
      |

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