Submission #825459

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
825459	2023-08-14T20:52:45 Z	ALeonidou	Highway Tolls (IOI18_highway)	C++17	0 / 100	105 ms	11480 KB

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));
    }
    //printVctPair2D(adj);
    
    vi v(m, 0);  
    b = ask(v);

    ll l, r, mid;

    //STEP 1 - Find edge and 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 e = l;
    ll p = U[l];

    //dbg2(e,p);

    //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){
        //dbg2(l,r);
        mid = MID;
        v.assign(m,0);
        for (ll i =0; i<sz(dis[mid]); i++){
            v[dis[mid][i]] =1;
        }

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

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

        long long c = ask(v);
        if (c > n){
            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];
    }
    //dbg2(e2,s);

    //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 0 13
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

*/

Compilation message

highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:94:8: warning: unused variable 'e' [-Wunused-variable]
   94 |     ll e = l;
      |        ^

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	208 KB	Output is incorrect: {s, t} is wrong.
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	336 KB	Output is incorrect: {s, t} is wrong.
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	1560 KB	Output is correct
2	Correct	15 ms	2900 KB	Output is correct
3	Correct	21 ms	4236 KB	Output is correct
4	Incorrect	105 ms	11480 KB	Output is incorrect: {s, t} is wrong.
5	Halted	0 ms	0 KB	-