oj.uz

Submission #824732

# Submission time Handle Problem Language Result Execution time Memory
824732 2023-08-14T09:14:48 Z ALeonidou Highway Tolls (IOI18_highway) C++17
12 / 100
 81 ms 9784 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 = (long long)(f / ((long long)(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 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 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 0 ms 220 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 336 KB Output is correct
2 Correct 7 ms 1104 KB Output is correct
3 Correct 78 ms 8128 KB Output is correct
4 Correct 69 ms 8140 KB Output is correct
5 Correct 62 ms 8028 KB Output is correct
6 Correct 67 ms 7952 KB Output is correct
7 Correct 53 ms 8036 KB Output is correct
8 Correct 81 ms 8120 KB Output is correct
9 Correct 61 ms 7900 KB Output is correct
10 Correct 64 ms 8112 KB Output is correct
11 Correct 77 ms 9052 KB Output is correct
12 Correct 72 ms 9784 KB Output is correct
13 Correct 78 ms 9196 KB Output is correct
14 Correct 70 ms 8524 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1808 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 8 ms 1284 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 7 ms 1232 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -