Submission #1159844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159844		modwwe	Highway Tolls (IOI18_highway)	C++20	100 / 100	115 ms	21208 KiB

highway

#include "highway.h"
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int   long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe  ll t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "ftree"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l,ll r)
{
    return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const ll inf = 4e18+1;
const ll mod2 = 1e9+7;
//const ll base=67;
ll  n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
ll  i, s10, s12,k1,k2,k3,s11,lim,w,l,r,dem5,dem6,dem7,dem9,now,root,q,start,en;
ll kk;
ll el = 19;
ll cost[2];
struct ib
{
    ll a,b;
};
vector<ib> ke[90001],a;
vector<int> v;
ll go[90001],floy,dia;
ll dist[90001];
bool check[130001];
void bfs(ll x)
{
    deque<ib> q;
    memset(go,-1,sizeof go);
    q.push_front({0,x});
    while(!q.empty())
    {
        ib x=q.front();
        q.pop_front();
        if(go[x.b]!=-1) continue;
        go[x.b]=x.a;
        for(auto f:ke[x.b])
            if(!check[f.b])
                q.pb({x.a+1,f.a});
    }
}
bool cmpp(ib a,ib b)
{
    return a.a>b.a;
}
ll dnc(vector<ib>a)
{
    if(a.size()==0) assert(0);
    if(a.size()==1) return a[0].a;
    ll mid=a.size()/2;
    vector<ib> cd;
    vector<int>haha=v;
    for(ll i=0; i<mid; i++)
        for(auto x:ke[a[i].a])
            haha[x.b]=1;
    if(ask(haha)==floy)for(ll i=mid; i<a.size(); i++)cd.pb(a[i]);
    else for(ll i=0; i<mid; i++)cd.pb(a[i]);
    return dnc(cd);
}
void find_pair(int N,vector<int> U,vector<int> V,int A,int B)
{
    n=N;
    m=U.size();
    ll min_cost=A;
    ll max_cost=B;
    for(ll i=0; i<m; i++)
        ke[U[i]].pb({V[i],i}),
        ke[V[i]].pb({U[i],i});
    for(ll i=0; i<m; i++)v.pb(0);
    floy=ask(v);
    dia=floy/A;
    l=0;
    r=m-2;
    while(l<=r)
    {
        ll mid=l+r>>1;
        for(ll i=0; i<=mid; i++)
            v[i]=1;
        if(ask(v)!=floy)r=mid-1;
        else l=mid+1;
        for(ll i=0; i<=mid; i++)
            v[i]=0;
    }
    r++;
    for(ll i=0; i<r; i++)
        check[i]=1;
    for(ll i=0; i<r; i++)
        v[i]=1;
    bfs(U[r]);
    for(ll i=0; i<n; i++)
        if(go[i]!=-1)
            a.pb({go[i],i});
    root=r;
    sort(a.begin(),a.end(),cmpp);
    l=0;
    r=a.size()-2;
    while(l<=r)
    {
        ll mid=l+r>>1;
        vector<int> hihi=v;
        for(ll i=0; i<=mid; i++)
            for(auto x:ke[a[i].b])
                hihi[x.b]=1;
        if(ask(hihi)!=floy)r=mid-1;
        else l=mid+1;
    }
    ll pos1=a[r+1].b;
    for(ll i=0; i<n; i++)
        dist[i]=go[i];
    bfs(a[r+1].b);
    a.clear();
    for(ll i=0; i<n; i++)
        if(go[i]==dia&&dist[i]+dist[pos1]==dia)
            a.pb({i,i});
    ll pos2;
    pos2=dnc(a);
    answer(pos1,pos2);
}

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