oj.uz

Submission #288274

# Submission time Handle Problem Language Result Execution time Memory
288274 2020-09-01T11:17:28 Z andrew Highway Tolls (IOI18_highway) C++17
51 / 100
 326 ms 21272 KB 
#include <bits/stdc++.h>
#include "highway.h"

#define fi first
#define se second
#define p_b push_back
#define m_p make_pair
#define sz(x) (int)x.size()
#define pii pair <int, int>
#define all(x) x.begin(),x.end()

using namespace std;
typedef long long ll;

vector < vector <pii> > v;
vector <int> p, tin, tout, nm, order, deep;
vector  <vector <int> > level;
int _timer;

void dfs(int x, int pr, int gl){
    p[x] = pr;
    tin[x] = ++_timer;
    order.p_b(x);
    deep[x] = gl;
    level[gl].p_b(x);
    for(auto to : v[x])if(to.fi != pr){
        dfs(to.fi, x, gl + 1);
        nm[to.fi] = to.se;
    }
    tout[x] = _timer;
}

void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
    int m = U.size();
    _timer = 0;
    tin.resize(n);
    tout.resize(n);
    p.resize(n);
    v.resize(n);
    nm.resize(n);
    deep.resize(n);
    level.resize(n);

    vector <int> w(m, 0);
    ll dist = ask(w);
    ll Len = dist / A;

    for(int i = 0; i < m; i++){
        v[U[i]].p_b({V[i], i});
        v[V[i]].p_b({U[i], i});
    }

    dfs(0, -1, 0);

    int Lca = -1;
    int l = 0, r = n - 1;
    while(l < r){
        int mid = (l + r) >> 1;
        fill(all(w), 0);
        for(int i = 0; i <= mid; i++){
            for(auto j : v[order[i]])if(j.fi != p[order[i]])w[j.se] = 1;
        }
        if(ask(w) == dist)l = mid + 1;
        else r = mid;
    }
    Lca = order[l];
    l = 0, r = n;
    while(l < r){
        int mid = (l + r) >> 1;
        fill(all(w), 0);
        for(int i = mid + 1; i < n; i++)w[nm[order[i]]] = 1;
        if(ask(w) != dist)l = mid + 1;
        else r = mid;
    }
    int S = order[l];
    int T = -1;
    ll ost = Len - (deep[S] - deep[Lca]);
    vector <int> mb;
    for(int i : level[ost + deep[Lca]]){
        if(tin[Lca] <= tin[i] && tout[i] <= tout[Lca])mb.p_b(i);
    }
    l = 0, r = sz(mb) - 1;
    while(l < r){
        int mid = (l + r) >> 1;
        fill(all(w), 0);
        for(int i = 1; i < tin[mb[mid]]; i++)w[nm[order[i]]] = 1;;
        if(ask(w) < dist + ost * (B - A))l = mid + 1;
        else r = mid;

    }
    T = mb[l];
    answer(S, T);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 15 ms 1664 KB Output is correct
3 Correct 153 ms 12496 KB Output is correct
4 Correct 176 ms 12444 KB Output is correct
5 Correct 180 ms 12456 KB Output is correct
6 Correct 170 ms 12372 KB Output is correct
7 Correct 160 ms 12424 KB Output is correct
8 Correct 174 ms 12640 KB Output is correct
9 Correct 176 ms 12404 KB Output is correct
10 Correct 181 ms 12476 KB Output is correct
11 Correct 188 ms 14020 KB Output is correct
12 Correct 191 ms 14852 KB Output is correct
13 Correct 195 ms 14256 KB Output is correct
14 Correct 201 ms 13384 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2688 KB Output is correct
2 Correct 27 ms 4992 KB Output is correct
3 Correct 43 ms 7360 KB Output is correct
4 Correct 133 ms 21180 KB Output is correct
5 Correct 132 ms 21180 KB Output is correct
6 Correct 127 ms 21172 KB Output is correct
7 Correct 130 ms 21188 KB Output is correct
8 Correct 130 ms 21172 KB Output is correct
9 Correct 136 ms 21272 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 15 ms 1664 KB Output is correct
3 Correct 201 ms 9844 KB Output is correct
4 Correct 309 ms 12420 KB Output is correct
5 Correct 274 ms 12576 KB Output is correct
6 Correct 287 ms 12412 KB Output is correct
7 Correct 280 ms 12532 KB Output is correct
8 Correct 269 ms 12444 KB Output is correct
9 Correct 180 ms 12484 KB Output is correct
10 Correct 221 ms 12448 KB Output is correct
11 Correct 261 ms 13132 KB Output is correct
12 Correct 251 ms 15132 KB Output is correct
13 Correct 261 ms 14240 KB Output is correct
14 Correct 271 ms 14888 KB Output is correct
15 Correct 192 ms 12556 KB Output is correct
16 Correct 215 ms 12416 KB Output is correct
17 Correct 248 ms 14556 KB Output is correct
18 Correct 326 ms 13940 KB Output is correct
19 Correct 250 ms 12508 KB Output is correct
20 Correct 282 ms 15732 KB Output is correct
21 Correct 142 ms 13568 KB Output is correct
22 Correct 197 ms 13592 KB Output is correct
23 Correct 158 ms 13144 KB Output is correct
24 Correct 177 ms 13952 KB Output is correct
25 Correct 178 ms 19784 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 5632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 5496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -