Submission #825929

#	Time	Username	Problem	Language	Result	Execution time	Memory
825929		ALeonidou	Highway Tolls (IOI18_highway)	C++17	18 / 100	147 ms	12480 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;
     
          	if (calls == 60){
            	cout<<"hello";
              	return;
            }	
          	calls++;
            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;
     	
          	if (calls == 60){
            	cout<<"hello";
              	return;
            }	
          	calls++;
            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;
     
          	if (calls == 60){
            	cout<<"hello";
              	return;
            }	
          	calls++;
            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<<"hello";
              	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
     
    */

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:81:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   81 |             for (ll i = 0; i<=mid; i++)
      |             ^~~
highway.cpp:84:12: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   84 |            if (calls == 60){
      |            ^~
highway.cpp:126:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  126 |             for (ll i =0; i<sz(dis[mid]); i++)
      |             ^~~
highway.cpp:129:12: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  129 |            if (calls == 60){
      |            ^~
highway.cpp:149:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  149 |             for (ll i=0; i<=mid; i++)
      |             ^~~
highway.cpp:152:12: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  152 |            if (calls == 60){
      |            ^~
highway.cpp:191:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  191 |             for (ll i = 0; i<= mid; i++)
      |             ^~~
highway.cpp:194:12: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  194 |            if (calls == 60){
      |            ^~

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