oj.uz

Submission #824710

# Submission time Handle Problem Language Result Execution time Memory
824710 2023-08-14T09:03:45 Z ALeonidou Highway Tolls (IOI18_highway) C++17
5 / 100
 85 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 / (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);

        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 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 0 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 0 ms 256 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 208 KB Output is correct
12 Correct 1 ms 256 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 6 ms 1104 KB Output is correct
3 Correct 67 ms 8116 KB Output is correct
4 Correct 75 ms 8096 KB Output is correct
5 Correct 80 ms 8096 KB Output is correct
6 Correct 68 ms 7956 KB Output is correct
7 Correct 73 ms 8016 KB Output is correct
8 Correct 85 ms 8116 KB Output is correct
9 Correct 64 ms 7924 KB Output is correct
10 Correct 71 ms 8116 KB Output is correct
11 Correct 68 ms 8988 KB Output is correct
12 Correct 66 ms 9792 KB Output is correct
13 Correct 69 ms 9208 KB Output is correct
14 Incorrect 71 ms 8524 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 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 380 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 6 ms 1272 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 1232 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -