제출 #714004

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
714004		victor_gao	통행료 (IOI18_highway)	C++17	51 / 100	180 ms	13432 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<pii>g[90015];
vector<int>all[90015];
vector<int>qry;
ll n,m,mx,mn,a,b,fa[90015],dep[90015];
void bfs(int root){
    for (int i=0;i<=n;i++){
        fa[i]=0; dep[i]=0; mx=0;
        all[i].clear();
    }
    queue<int>q; q.push(root);
    dep[root]=1; mx=1;
    all[1].push_back(root);
    while (!q.empty()){
        int p=q.front(); q.pop();
        for (auto [i,idx]:g[p]){
            if (!dep[i]){
                dep[i]=dep[p]+1; fa[i]=idx; mx=max(mx,dep[i]);
                all[dep[i]].push_back(i);
                q.push(i);
            }
        }
    }
}
int solve1(int root){
    bfs(root);
    int l=1,r=mx+1;
    while (l<r){
        int mid=(l+r)>>1;
        for (int j=0;j<=mid;j++){
            for (auto i:all[j])
                qry[fa[i]]=1;
        }
        ll dis=ask(qry);
        if (dis==b*(mn/a)) r=mid;
        else l=mid+1;
        for (int j=0;j<=mid;j++){
            for (auto i:all[j])
                qry[fa[i]]=0;
        }
    }
    int p=l;
    l=0,r=all[p].size();
    while (l<r){
        int mid=(l+r)>>1;
        for (int j=l;j<=mid;j++)
            qry[fa[all[p][j]]]=1;
        ll dis=ask(qry);
        for (int j=l;j<=mid;j++)
            qry[fa[all[p][j]]]=0;
        if (dis!=mn) r=mid;
        else l=mid+1;
    }
    return all[p][l];
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    n=N; m=U.size(); a=A; b=B;
    for (int i=0;i<m;i++){
        g[U[i]].push_back({V[i],i});
        g[V[i]].push_back({U[i],i});
    }
    qry.resize(m,0);
    mn=ask(qry);
    ll root=0;
    ll s=solve1(root),d=mn/A;
    bfs(s);
    ll p=d+1,l=0,r=all[p].size();
    while (l<r){
        ll mid=(l+r)>>1;
        for (int j=l;j<=mid;j++)
            qry[fa[all[p][j]]]=1;
        ll dis=ask(qry);
        for (int j=l;j<=mid;j++)
            qry[fa[all[p][j]]]=0;
        if (dis!=mn) r=mid;
        else l=mid+1;
    }
    ll t=all[p][l];
    answer(s,t);
}
/*
./rand
./highway
*/

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