Submission #825948

#	Time	Username	Problem	Language	Result	Execution time	Memory
825948		ALeonidou	Highway Tolls (IOI18_highway)	C++17	18 / 100	109 ms	12364 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
         
        ll calls= 1;
         
        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;
         
              	if (calls == 60){
                	cout<<calls<<endl;
                  	return;
                }	
              	calls++;
                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