Submission #1232713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232713		Hamed_Ghaffari	Highway Tolls (IOI18_highway)	C++20	100 / 100	145 ms	15364 KiB

highway

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

using ll = long long;

const int MXN = 9e4+5;

void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
    int m = U.size();
    vector<int> w(m, 0);
    ll D = ask(w);
    int l=-1, r=m-1, mid;
    while(r-l>1) {
        mid = (l+r)>>1;
        fill(w.begin(), w.begin()+mid+1, 1);
        (ask(w)==D ? l : r) = mid;
        fill(w.begin(), w.begin()+mid+1, 0);
    }
    fill(w.begin(), w.begin()+r, 1);
    vector<vector<int>> g = vector<vector<int>>(n);
    vector<vector<int>> adj = vector<vector<int>>(n);
    vector<vector<int>> dis = vector<vector<int>>(2, vector<int>(n));
    auto bfs = [&](int v, int id) -> vector<int> {
        fill(dis[id].begin(), dis[id].end(), -1);
        dis[id][v] = 0;
        queue<int> q;
        q.push(v);
        vector<int> res;
        while(!q.empty()) {
            int v = q.front(); q.pop();
            res.push_back(v);
            for(int u : g[v])
                if(dis[id][u]==-1) {
                    dis[id][u] = dis[id][v]+1;
                    q.push(u);
                }
        }
        return res;
    };
    for(int i=r; i<m; i++)
        g[U[i]].push_back(V[i]),
        g[V[i]].push_back(U[i]);
    bfs(U[r], 0);
    bfs(V[r], 1);
    vector<int> mark(n, 0);
    for(int i=0; i<n; i++)
        if(dis[0][i]<dis[1][i]) mark[i] = 1;
        else if(dis[0][i]>dis[1][i]) mark[i] = 2;
    auto solve = [&](int id) -> int {
        for(int i=0; i<n; i++) g[i].clear();
        for(int i=0; i<n; i++) adj[i].clear();
        for(int i=r; i<m; i++)
            if(mark[U[i]]==id && mark[V[i]]==id)
                g[U[i]].push_back(V[i]),
                g[V[i]].push_back(U[i]),
                adj[U[i]].push_back(i),
                adj[V[i]].push_back(i);
        vector<int> ord = bfs(id==1 ? U[r] : V[r], 0);
        int l2=0, r2=ord.size();
        while(r2-l2>1) {
            mid = (l2+r2)>>1;
            for(int i=mid; i<ord.size(); i++)
                for(int j : adj[ord[i]])
                    w[j] = 1;
            (ask(w)==D ? r2 : l2)=mid;
            for(int i=mid; i<ord.size(); i++)
                for(int j : adj[ord[i]])
                    w[j] = 0;
        }
        return ord[l2];
    };
    answer(solve(1), solve(2));
}

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