Submission #298866

#	Time	Username	Problem	Language	Result	Execution time	Memory
298866		muhammad_hokimiyon	Highway Tolls (IOI18_highway)	C++14	0 / 100	42 ms	12416 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define dl double long

const int maxn = 200100;

int m;
ll dist;
bool used[maxn];
int h[maxn];
int pa[maxn];
vector < int > nnj,f;
vector < pair < int , int > > v[maxn],g[maxn];

void dfs( int x , int p , int id )
{
    h[x] = h[p] + 1;
    f.push_back(x);
    pa[x] = id;
    for(  auto y : g[x] ){
        if( y.fi != p ){
            dfs( y.fi , x , y.se );
        }
    }
}

int solve( int x )
{
    f.clear();
    h[x] = 0;
    dfs( x , x , -1 );
    vector < pair < int , int > > v;
    for( int i = 0; i < (int)f.size(); i++ ){
        v.push_back({ h[f[i]] , f[i] });
    }
    sort( v.rbegin() , v.rend() );
    int l = 0 , r = (int)v.size() - 1;
    int res = (int)v.size() - 1;
    while( l <= r ){
        int mi = (l + r) / 2;
        vector < int > w(m , 0);
        for( auto y : nnj ){
            w[y] = 1;
        }
        for( int i = 0; i <= mi; i++ ){
            if( pa[v[i].se] != -1 ){
                w[pa[v[i].se]] = 1;
            }
        }
        ll di = ask( w );
        if( di > dist ){
            res = min( res , mi );
            r = mi - 1;
        }else l = mi + 1;
    }
    return v[res].se;
}

void bfs( int x , int y )
{
    vector < int > d(maxn , 1e9);
    vector < int > p(maxn , -1);
    d[x] = d[y] = 0;
    queue < int > q;
    q.push(x);
    q.push(y);
    while( !q.empty() ){
        int x = q.front();
        q.pop();
        for( auto y : v[x] ){
            if( d[y.fi] == 1e9 ){
                d[y.fi] = d[x] + 1;
                used[y.se] = true;
                g[x].push_back(y);
                g[y.fi].push_back({ x , y.se });
                q.push(y.fi);
            }
        }
    }
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
    m = (int)U.size();
    vector < int > a,b;
    vector < int > w(m , 0);
    dist = ask(w);
    for( int i = 0; i < m; i++ ){
        int x = U[i] , y = V[i];
        v[x].push_back({y , i});
        v[y].push_back({x , i});
    }
    int l = 0 , r = m - 1;
    while( l < r ){
        int mid = (l + r) / 2;
        vector < int > w(m , 0);
        for( int j = 0; j <= mid; j++ )w[j] = 1;
        ll x = ask( w );
        if( x == dist )l = mid + 1;
        else r = mid;
    }
    bfs( U[l] , V[l] );
    for( int i = 0; i < m; i++ ){
        if( used[i] )continue;
        nnj.push_back(i);
    }
    int ans1 = solve( U[l] );
    int ans2 = solve( V[l] );
    answer(ans1 , ans2);
}

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