oj.uz

Submission #825948

# Submission time Handle Problem Language Result Execution time Memory
825948 2023-08-15T09:29:07 Z ALeonidou Highway Tolls (IOI18_highway) C++17
18 / 100
 109 ms 12364 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;
         
                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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 208 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 0 ms 216 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 336 KB Output is correct
2 Correct 7 ms 1396 KB Output is correct
3 Correct 89 ms 10976 KB Output is correct
4 Correct 100 ms 10920 KB Output is correct
5 Correct 86 ms 10988 KB Output is correct
6 Correct 81 ms 10864 KB Output is correct
7 Correct 74 ms 10924 KB Output is correct
8 Correct 84 ms 10872 KB Output is correct
9 Correct 89 ms 11004 KB Output is correct
10 Correct 91 ms 10884 KB Output is correct
11 Correct 77 ms 10556 KB Output is correct
12 Correct 73 ms 10764 KB Output is correct
13 Correct 92 ms 10656 KB Output is correct
14 Correct 102 ms 10572 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1644 KB Output is correct
2 Correct 16 ms 2812 KB Output is correct
3 Correct 21 ms 4176 KB Output is correct
4 Correct 62 ms 11504 KB Output is correct
5 Correct 58 ms 11500 KB Output is correct
6 Correct 59 ms 11956 KB Output is correct
7 Correct 67 ms 12364 KB Output is correct
8 Correct 63 ms 11680 KB Output is correct
9 Correct 64 ms 11832 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 8 ms 1508 KB Output is correct
3 Correct 85 ms 8596 KB Output is correct
4 Correct 80 ms 10940 KB Output is correct
5 Correct 79 ms 10776 KB Output is correct
6 Correct 73 ms 10872 KB Output is correct
7 Correct 78 ms 10848 KB Output is correct
8 Correct 72 ms 10828 KB Output is correct
9 Correct 81 ms 10872 KB Output is correct
10 Correct 83 ms 11100 KB Output is correct
11 Correct 75 ms 10596 KB Output is correct
12 Correct 78 ms 10824 KB Output is correct
13 Correct 99 ms 10644 KB Output is correct
14 Correct 77 ms 10644 KB Output is correct
15 Correct 73 ms 10884 KB Output is correct
16 Correct 84 ms 10896 KB Output is correct
17 Correct 94 ms 10652 KB Output is correct
18 Correct 93 ms 10724 KB Output is correct
19 Correct 82 ms 10904 KB Output is correct
20 Correct 97 ms 10948 KB Output is correct
21 Correct 100 ms 12048 KB Output is correct
22 Correct 84 ms 12044 KB Output is correct
23 Correct 84 ms 11492 KB Output is correct
24 Incorrect 97 ms 11652 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1592 KB Output is correct
2 Correct 11 ms 1716 KB Output is correct
3 Incorrect 109 ms 11912 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1524 KB Output is correct
2 Incorrect 11 ms 1660 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -