oj.uz

Submission #1013299

# Submission time Handle Problem Language Result Execution time Memory
1013299 2024-07-03T11:50:13 Z c2zi6 Highway Tolls (IOI18_highway) C++14
12 / 100
 233 ms 262144 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "highway.h"

int n, m;
VVPI gp;
VI depth;
VI parind;

void dfs(int u = 0, int pind = -1) {
    parind[u] = pind;
    for (auto[v, ind] : gp[u]) if (ind != pind) {
        depth[v] = depth[u]+1;
        dfs(v, ind);
    }
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    n = N;
    m = U.size();
    gp = VVPI(n);
    rep(i, m) {
        gp[U[i]].pb({V[i], i});
        gp[V[i]].pb({U[i], i});
    }
    depth = parind = VI(n);
    dfs();
    ll base = ask(VI(m));
    int d = base/A;

    VI b;
    rep(u, n) if (depth[u] == d) b.pb(u);

    auto f = [&](int x) {
        VI W(m);
        replr(i, 0, x) W[parind[b[i]]] = true;
        return ask(W) > base;
    };

    int l = -1, r = b.size()-1;
    while (l + 1 < r) {
        int m = (l + r) / 2;
        if (f(m)) r = m;
        else l = m;
    }
    answer(0, b[r]);
}

/*ask(VI w);*/
/*answer(int s, int t)*/

Compilation message

highway.cpp: In function 'void dfs(int, int)':
highway.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     for (auto[v, ind] : gp[u]) if (ind != pind) {
      |              ^

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 6 ms 1276 KB Output is correct
3 Correct 70 ms 8488 KB Output is correct
4 Correct 55 ms 8464 KB Output is correct
5 Correct 72 ms 8496 KB Output is correct
6 Correct 63 ms 8412 KB Output is correct
7 Correct 65 ms 8440 KB Output is correct
8 Correct 80 ms 8488 KB Output is correct
9 Correct 60 ms 8272 KB Output is correct
10 Correct 68 ms 8644 KB Output is correct
11 Correct 59 ms 8800 KB Output is correct
12 Correct 64 ms 9200 KB Output is correct
13 Correct 61 ms 8784 KB Output is correct
14 Correct 67 ms 8524 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1624 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 344 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 233 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 222 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -