Submission #825462

#	Time	Username	Problem	Language	Result	Execution time	Memory
825462		ALeonidou	Highway Tolls (IOI18_highway)	C++17	18 / 100	137 ms	12360 KiB

highway

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

using namespace std;

#define ll int
typedef vector <ll> vi;
typedef pair <ll,ll > ii;
typedef vector <ii> vii;
#define sz(x) (ll)x.size()
#define pb push_back
#define F first
#define S second
#define MID ((l+r)/2)
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;

void tabb(ll n){
    for (ll i= 0; i<n; i++) cout<<"\t";
}

void printVct(vi &v){
    for (ll i=0; i<sz(v); i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
}

void printVctPair(vii &v){
    for (ll i=0; i<sz(v); i++){
        cout<<"("<<v[i].F<<","<<v[i].S<<") ";
    }
    cout<<endl;
}

void printVct2D(vector<vi> &adj){
    for (ll i=0; i<sz(adj); i++){
        cout<<i<<": ";
        for (ll j =0; j<sz(adj[i]); j++){
            cout<<"("<<adj[i][j]<<"),";
        }
        cout<<endl;
    }
    cout<<endl;
}

void printVctPair2D(vector<vii> &adj){
    for (ll i=0; i<sz(adj); i++){
        for (ll j =0; j<sz(adj[i]); j++){
            cout<<"("<<adj[i][j].F<<","<<adj[i][j].S<<"),";
        }
        cout<<endl;
    }
    cout<<endl;
}

vector <vii> adj;
ll n,m;
long long b;   //all light case value

void find_pair(int N, vi V, vi U, int A,int B) {
    n = N; m = sz(U);
    adj.assign(n, vii());
    for (ll i=0; i<m ;i++){
        adj[U[i]].pb(ii(V[i], i));
        adj[V[i]].pb(ii(U[i], i));
    }
    vi v(m, 0);  
    b = ask(v);

    ll l, r, mid;

    //STEP 1 - Find node on path from S to T
    l = 0, r = m-1;
    while (l < r){
        mid = MID;
        v.assign(m, 0);
        for (ll i = 0; i<=mid; i++) 
            v[i] = 1;

        long long c = ask(v);
        if (c > b) r = mid;
        else l = mid+1;
    }
    ll p = U[l];

    //STEP 2 - Find distance from S
    vi disNode(n);
    vector <vi> dis(n, vi());
    ll h = 0;
    queue <ii> q;
    vi vis(n, 0);
    q.push(ii(p,0));
    while (!q.empty()){
        ii f = q.front();
        q.pop();
        
        ll u = f.F;
        ll level = f.S;

        h = max(level, h);
        disNode[u] = level;

        vis[u] = 1;
        for (ll i= 0; i<sz(adj[u]); i++){
            if (!vis[adj[u][i].F]){
                q.push(ii(adj[u][i].F,level+1));
                dis[level+1].pb(adj[u][i].S);
            }
        }
    }
    //printVct2D(dis);
    l = 1, r = h;
    ll maxDis = 0;
    while (l <= r){
        mid = MID;
        v.assign(m,0);
        for (ll i =0; i<sz(dis[mid]); i++) 
            v[dis[mid][i]] =1;

        long long c = ask(v);
        if (c > b){
            l = mid + 1;
            maxDis = mid;
        }
        else{
            r = mid - 1;
        }
    }

    //STEP 3 - Find S
    l = 0, r = sz(dis[maxDis]) -1;
    while (l < r){
        mid = MID;
        v.assign(m, 0);
        for (ll i=0; i<=mid; i++)
            v[dis[maxDis][i]] = 1;

        long long c = ask(v);
        if (c > b) r = mid;
        else l = mid + 1;
    }
    ll e2 = dis[maxDis][l],s;
    if (disNode[U[e2]] > disNode[V[e2]]) s = U[e2];
    else s = V[e2];

    //STEP 4 - Find T
    vi canditates;
    ll st = b / A;
    q.push(ii(s, 0));
    vis.assign(n ,0);
    while (!q.empty()){
        ii f = q.front();
        q.pop();
        ll u = f.F;
        ll level = f.S;
        vis[u] =1 ;
        disNode[u] = level;
        for(ll i =0; i<sz(adj[u]); i++){
            if (!vis[adj[u][i].F]){
                q.push(ii(adj[u][i].F, level +1));
                if (level + 1 == st){
                    canditates.pb(adj[u][i].S);
                }
            }
        }
    }
    //printVct(canditates);
    l = 0, r = sz(canditates)-1;
    while (l < r){
        mid = MID;
        v.assign(m , 0);
        for (ll i = 0; i<= mid; i++)
            v[canditates[i]] = 1;

        long long c = ask(v);
        if (c > b) r = mid;
        else l = mid+1;
    }
    ll e3 = canditates[l],t;
    if (disNode[U[e3]] > disNode[V[e3]]) t = U[e3];
    else t = V[e3];
    //dbg2(e3, t);

    //dbg2(s, t);
    answer(s, t);
}

/*
14 13 2 5 3 10
0 1
1 5
1 2
2 3
1 4
5 7
7 8
5 6
3 12
3 11
2 9
9 10
9 13

*/

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