제출 #1244919

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1244919		jeroenodb	Highway Tolls (IOI18_highway)	C++20	100 / 100	123 ms	9952 KiB

highway

#include "highway.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) begin(x),end(x)
const int oo = 1e9;
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    int m = U.size();
    int n = N;
    vi w(m);
    ll dist = ask(w)/A;
    vvi adj(n);
    for(int i=0;i<m;++i) {
        adj[U[i]].push_back(V[i]);
        adj[V[i]].push_back(U[i]);
    }
    int lo = 1, hi = m;
    while(lo<hi) {
        int mid = (lo+hi)/2;
        w.assign(m,1);
        fill(w.begin(),w.begin()+mid,0);
        if(ask(w)==dist*ll(A)) {
            // great, some shortest path!
            hi = mid;
        } else lo = mid+1;
    }
    auto bfs = [&](int s) {
        vi d(n,oo);
        d[s]=0;
        vi q = {s};
        for(int i=0;i<n;++i) {
            int at = q[i];
            for(int to : adj[at]) if(d[to]==oo) {
                d[to]=d[at]+1;
                q.push_back(to);
            }
        }
        return d;
    };
    // const int M = lo;

    lo--;
    auto du = bfs(U[lo]);
    auto dv = bfs(V[lo]);
    vi su,sv;
    for(int i=0;i<n;++i) {
        if(du[i]==dv[i]+1 and dv[i]<dist) {
            sv.push_back(i);
        } else if(du[i]+1==dv[i] and du[i]<dist) {
            su.push_back(i);
        }
    }
    // int lu,lv;
    {
        // vector<bool> good(n);
        // vector<bool> done(n);
        // for(int i : su) if(du[i]<dist) good[i]=1;
        // w.assign(m,1);
        // for(int i=0;i<M;++i) {
        //     int u = U[i], v = V[i];
        //     if(du[u]>du[v]) swap(u,v);
        //     if(!done[v] and good[u] and good[v]) {
        //         w[i]=0;
        //         done[v]=1;
        //     };
        // }
        // ll have = ask(w);
        // // A*lu + B*(lv+1) == have
        // // lu+(lv+1)==dist
        // // (lv+1) == dist-lu
        // // A*lu + B*(dist-lu) == have
        // // (A-B)*lu = have-B*dist
        // lu = (have-ll(B)*dist)/(A-B);
        // lv = dist-1-lu;
    }
    auto solve = [&](vi special, vi d) {
        // special.erase(partition(all(special),[&](int i) {return d[i]==l;}),special.end());       
        int k = special.size();
        sort(all(special),[&](int i, int j) {
            return d[i]>d[j];
        });
        int lo = 1, hi = k;
        while(lo<hi) {
            fill(all(w),0);
            vector<bool> want(n);

            int mid = (lo+hi)/2;
            for(int i=0;i<mid;++i) want[special[i]]=1;
            for(int i=0;i<m;++i) {
                int u = U[i], v = V[i];
                if(want[v]) swap(u,v);
                if(want[u] and !want[v]) {
                    w[i]=1;
                }
            }
            ll my = ask(w);
            if(my != dist*A) {
                hi = mid;
            } else lo = mid+1;

        }
        return special[lo-1];
    };
    int s = solve(su,du);
    int t = solve(sv,dv);
    answer(s,t);


}

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