oj.uz

Submission #824739

# Submission time Handle Problem Language Result Execution time Memory
824739 2023-08-14T09:19:19 Z ALeonidou Highway Tolls (IOI18_highway) C++17
12 / 100
 84 ms 9792 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 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;
vi vis;
void dfs(ll u, ll s, ll t, vii &canditates){
    vis[u] = 1;
    for (ll i=0; i<sz(adj[u]); i++){
        if (!vis[adj[u][i].F]){
            dfs(adj[u][i].F,s + 1, t, canditates);
            if (s == t-1){
                canditates.pb(adj[u][i]);
            }
        }
    }
}

void find_pair(int n, vi V, vi U, int a,int b) {
    //subtask 1+2
    ll m = sz(U);
    //dbg2(n,m);
    adj.assign(n, vii());
    for (ll i=0; i<m ;i++){
        //dbg2(U[i], V[i]);
        adj[U[i]].pb(ii(V[i], i));
        adj[V[i]].pb(ii(U[i], i));
    }
    //printVctPair2D(adj);
    
    vi v(m, 0);
    long long f = ask(v);
    ll dis = f / a;
    
    vii canditates;     //(node, edge)
    vis.assign(n, 0);
    dfs(0, 0, dis, canditates);

    //printVctPair(canditates);

    ll l = 0, r = sz(canditates)-1,mid;
    while (l < r){
        mid  = MID;
        //dbg3(l,r,mid);
        v.assign(m,0);
        for (ll i = 0; i<=mid; i++){    //select left part
            v[canditates[i].S] = 1;
        }

        //printVct(v);

        long long cur = ask(v);

        if (cur > f){
            r  = mid;
        }
        else{
           l = mid+1;
        }  
    }
    ll t = canditates[l].F;
    //dbg(t);
    answer(0, t);
}

/*
14 13 2 5 0 13
0 1
1 5
1 4
1 2
2 3
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 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 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 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 0 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 380 KB Output is correct
2 Correct 6 ms 1104 KB Output is correct
3 Correct 68 ms 8116 KB Output is correct
4 Correct 84 ms 8092 KB Output is correct
5 Correct 64 ms 8096 KB Output is correct
6 Correct 61 ms 7948 KB Output is correct
7 Correct 72 ms 8020 KB Output is correct
8 Correct 64 ms 8124 KB Output is correct
9 Correct 55 ms 7904 KB Output is correct
10 Correct 82 ms 8104 KB Output is correct
11 Correct 78 ms 8924 KB Output is correct
12 Correct 65 ms 9792 KB Output is correct
13 Correct 66 ms 9192 KB Output is correct
14 Correct 58 ms 8392 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1872 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1232 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1284 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -