oj.uz

Submission #825461

# Submission time Handle Problem Language Result Execution time Memory
825461 2023-08-14T20:59:59 Z ALeonidou Highway Tolls (IOI18_highway) C++17
5 / 100
 122 ms 25424 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

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;

        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 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 10 ms 1372 KB Output is correct
3 Correct 113 ms 10968 KB Output is correct
4 Correct 75 ms 11016 KB Output is correct
5 Correct 110 ms 10984 KB Output is correct
6 Correct 110 ms 10864 KB Output is correct
7 Correct 94 ms 10912 KB Output is correct
8 Correct 82 ms 10868 KB Output is correct
9 Correct 96 ms 11012 KB Output is correct
10 Correct 95 ms 10928 KB Output is correct
11 Correct 85 ms 10584 KB Output is correct
12 Correct 107 ms 10792 KB Output is correct
13 Correct 119 ms 10676 KB Output is correct
14 Incorrect 112 ms 10688 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1616 KB Output is correct
2 Correct 14 ms 2896 KB Output is correct
3 Correct 22 ms 4296 KB Output is correct
4 Correct 66 ms 11444 KB Output is correct
5 Correct 64 ms 11544 KB Output is correct
6 Correct 63 ms 12064 KB Output is correct
7 Correct 97 ms 12476 KB Output is correct
8 Correct 101 ms 11680 KB Output is correct
9 Runtime error 73 ms 25424 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 13 ms 1480 KB Output is correct
3 Correct 55 ms 8596 KB Output is correct
4 Correct 85 ms 10852 KB Output is correct
5 Correct 72 ms 10776 KB Output is correct
6 Correct 85 ms 10956 KB Output is correct
7 Correct 97 ms 10812 KB Output is correct
8 Correct 71 ms 10824 KB Output is correct
9 Runtime error 96 ms 21868 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1528 KB Output is correct
2 Correct 13 ms 1688 KB Output is correct
3 Incorrect 122 ms 12040 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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