oj.uz

Submission #825929

# Submission time Handle Problem Language Result Execution time Memory
825929 2023-08-15T09:25:09 Z ALeonidou Highway Tolls (IOI18_highway) C++17
18 / 100
 147 ms 12480 KB 
    #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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 7 ms 1380 KB Output is correct
3 Correct 79 ms 11068 KB Output is correct
4 Correct 106 ms 10924 KB Output is correct
5 Correct 107 ms 10988 KB Output is correct
6 Correct 94 ms 10856 KB Output is correct
7 Correct 102 ms 10924 KB Output is correct
8 Correct 96 ms 10900 KB Output is correct
9 Correct 86 ms 11012 KB Output is correct
10 Correct 109 ms 10924 KB Output is correct
11 Correct 91 ms 10568 KB Output is correct
12 Correct 79 ms 10852 KB Output is correct
13 Correct 101 ms 10576 KB Output is correct
14 Correct 73 ms 10580 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1520 KB Output is correct
2 Correct 15 ms 2872 KB Output is correct
3 Correct 36 ms 4168 KB Output is correct
4 Correct 62 ms 11504 KB Output is correct
5 Correct 81 ms 11584 KB Output is correct
6 Correct 82 ms 12064 KB Output is correct
7 Correct 63 ms 12480 KB Output is correct
8 Correct 101 ms 11792 KB Output is correct
9 Correct 62 ms 11800 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 12 ms 1488 KB Output is correct
3 Correct 51 ms 8604 KB Output is correct
4 Correct 86 ms 10848 KB Output is correct
5 Correct 73 ms 10832 KB Output is correct
6 Correct 104 ms 10884 KB Output is correct
7 Correct 76 ms 10836 KB Output is correct
8 Correct 95 ms 10856 KB Output is correct
9 Correct 76 ms 10872 KB Output is correct
10 Correct 108 ms 10992 KB Output is correct
11 Correct 91 ms 10608 KB Output is correct
12 Correct 101 ms 10832 KB Output is correct
13 Correct 89 ms 10720 KB Output is correct
14 Correct 112 ms 10716 KB Output is correct
15 Correct 73 ms 10892 KB Output is correct
16 Correct 74 ms 10964 KB Output is correct
17 Correct 84 ms 10572 KB Output is correct
18 Correct 93 ms 10700 KB Output is correct
19 Correct 108 ms 10828 KB Output is correct
20 Correct 100 ms 10880 KB Output is correct
21 Correct 72 ms 12036 KB Output is correct
22 Correct 99 ms 12052 KB Output is correct
23 Correct 82 ms 11496 KB Output is correct
24 Incorrect 91 ms 11704 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
25 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1588 KB Output is correct
2 Correct 11 ms 1616 KB Output is correct
3 Incorrect 147 ms 11920 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1556 KB Output is correct
2 Incorrect 14 ms 1668 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -