oj.uz

Submission #824309

# Submission time Handle Problem Language Result Execution time Memory
824309 2023-08-14T00:58:28 Z ALeonidou Highway Tolls (IOI18_highway) C++17
5 / 100
 106 ms 10264 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){
    // tabb(tab);
    // dbg3(u,s,t);
    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(ii(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);

        ll 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 8
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 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 0 ms 208 KB Output is correct
6 Correct 1 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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 6 ms 1104 KB Output is correct
3 Correct 84 ms 8108 KB Output is correct
4 Correct 62 ms 8096 KB Output is correct
5 Correct 106 ms 8092 KB Output is correct
6 Correct 104 ms 7956 KB Output is correct
7 Correct 95 ms 8012 KB Output is correct
8 Correct 92 ms 8124 KB Output is correct
9 Correct 58 ms 7904 KB Output is correct
10 Correct 62 ms 8132 KB Output is correct
11 Correct 89 ms 9312 KB Output is correct
12 Correct 59 ms 10264 KB Output is correct
13 Correct 96 ms 9564 KB Output is correct
14 Incorrect 74 ms 8668 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 Incorrect 6 ms 1912 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 1360 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 10 ms 1360 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -