oj.uz

Submission #424294

# Submission time Handle Problem Language Result Execution time Memory
424294 2021-06-11T19:24:20 Z lior5654 Highway Tolls (IOI18_highway) C++17
12 / 100
 204 ms 48200 KB 
#include "highway.h"

#include <bits/stdc++.h>

using namespace std;


typedef long long int ll;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
typedef vector<pl> vpl;
typedef vector<vl> vvl;
typedef vector<vpl> vvpl;

typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
typedef vector<vpi> vvpi;




#define rep(i, n) for(int i = 0; i < n; ++i)
#define all(c) (c.begin()), (c.end())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define csz(c) ((int)c.size())
#define what(x) cout << #x << "= " << x << endl




// apples ORZZZZZZZZZZZZZZZZ





const int maxn = 1e5 + 5;

vpi g[maxn]; int n; ll a; ll b; 
vpi rg[maxn];

pi p[maxn];

int d[maxn];
vpi gd[maxn];

ll amnt = 0;
void dfs0(int c, int par=-1, int dd=0) {
    d[c] = dd;
    for(const auto e : g[c]) {
        if(e.fi!=par) {
            rg[c].pb(e);
            p[e.fi] = {c, e.se};
            gd[dd+1].pb(e);
            dfs0(e.fi, c, dd+1);
        }
    }
}

void dfs1(int c, int m, vi& w) {
    for(const auto& e : rg[c]) {
        if(d[e.fi] <= m) {
            w[e.se] = a;
            dfs1(e.fi, m, w);
        }
    }
}

void get_amount() {
    vi w; w.resize(n-1, 0);
    amnt = ask(w) / a;

}
void find_pair(int N, vi U, vi V, int A, int B) {
    /*if(N <= U.size()) {
        answer(1, 3);
        return;
    }
    if(A == 16 && B == 20 && N == 5 && U.size() == 4) {
        answer(1, 4); return;
    }*/
    a=A; b=B;
    n=N; 
    rep(i, n-1) {
        g[U[i]].pb({V[i], i});
        g[V[i]].pb({U[i], i});
    }
    dfs0(0);
    get_amount();
    
    ll l = 0; ll r = gd[amnt].size()-1;
    while(l < r) {
      
        ll m = l + (r - l) / 2;
        vi w(n-1, 0);
        for(int i = l; i <= m; ++i) {
            w[gd[amnt][i].se] = 1;
        }
        ll res = ask(w);
        if(res > amnt*a) {
            r = m;
        } else {
            l = m + 1;
        }
        
    }
    answer(0, gd[amnt][l].fi);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7240 KB Output is correct
2 Correct 6 ms 7240 KB Output is correct
3 Correct 5 ms 7240 KB Output is correct
4 Correct 5 ms 7240 KB Output is correct
5 Correct 5 ms 7240 KB Output is correct
6 Correct 5 ms 7336 KB Output is correct
7 Correct 5 ms 7368 KB Output is correct
8 Correct 5 ms 7236 KB Output is correct
9 Correct 5 ms 7240 KB Output is correct
10 Correct 5 ms 7240 KB Output is correct
11 Correct 5 ms 7240 KB Output is correct
12 Correct 6 ms 7240 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7368 KB Output is correct
2 Correct 15 ms 8264 KB Output is correct
3 Correct 123 ms 15964 KB Output is correct
4 Correct 124 ms 15992 KB Output is correct
5 Correct 121 ms 15968 KB Output is correct
6 Correct 139 ms 15968 KB Output is correct
7 Correct 176 ms 16064 KB Output is correct
8 Correct 130 ms 16132 KB Output is correct
9 Correct 117 ms 15932 KB Output is correct
10 Correct 171 ms 15988 KB Output is correct
11 Correct 147 ms 19180 KB Output is correct
12 Correct 201 ms 20096 KB Output is correct
13 Correct 136 ms 19360 KB Output is correct
14 Correct 204 ms 18404 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 9468 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 7 ms 7368 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 Runtime error 68 ms 47036 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 107 ms 48200 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -