oj.uz

Submission #255343

# Submission time Handle Problem Language Result Execution time Memory
255343 2020-07-31T17:54:25 Z Erkhemkhuu Highway Tolls (IOI18_highway) C++17
51 / 100
 244 ms 19192 KB 
#include <bits/stdc++.h>
#include <highway.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
const int N = 150005;
pair <int, int> par[N];
vector <int> w;
vector < vector <pair <int, int> > > adj(N);
int flat[N], timer;
void dfs(int v, int p) {
    flat[timer++] = v;
    for(auto &u: adj[v]) {
        if(u.F == p) continue;
        par[u.F] = {v, u.S};
        dfs(u.F, v);
    }
    return;
}
void run(int l, int r, int type) {
    for(int i = l; i <= r; i++)
        w[par[flat[i]].S] = type;
    return;
}
int go(int l, int r, ll max_cost) {
    while(l + 1 < r) {
        int mid = (l + r) / 2;
        run(l, mid, 1);
        if(ask(w) < max_cost) l = mid;
        else {
            r = mid;
            run(l, mid, 0);
        }
    }
    return l + 1;
}
void find_pair(int n, vector <int> u, vector <int> v, int a, int b) {
    int i, m, s, t;
    ll max_cost;
    m = u.size();
    w.resize(m);
    for(i = 0; i < m; i++) {
        adj[u[i]].pb({v[i], i});
        adj[v[i]].pb({u[i], i});
    }
    dfs(0, -1);
    w.assign(m, 1);
    max_cost = ask(w);
    w.assign(m, 0);
    s = flat[go(1, n - 1, max_cost)];
    w.assign(m, 0);
    timer = 0;
    dfs(s, -1);
    t = flat[go(1, n - 1, max_cost)];
    assert(s >= 0 && s < n && t >= 0 && t < n);
    answer(s, t);
    return;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3968 KB Output is correct
2 Correct 18 ms 4480 KB Output is correct
3 Correct 203 ms 10144 KB Output is correct
4 Correct 201 ms 10104 KB Output is correct
5 Correct 180 ms 10112 KB Output is correct
6 Correct 210 ms 10252 KB Output is correct
7 Correct 149 ms 10104 KB Output is correct
8 Correct 235 ms 10232 KB Output is correct
9 Correct 136 ms 10224 KB Output is correct
10 Correct 127 ms 10232 KB Output is correct
11 Correct 186 ms 10584 KB Output is correct
12 Correct 175 ms 11172 KB Output is correct
13 Correct 205 ms 10676 KB Output is correct
14 Correct 145 ms 10756 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4992 KB Output is correct
2 Correct 41 ms 6008 KB Output is correct
3 Correct 35 ms 7196 KB Output is correct
4 Correct 99 ms 13816 KB Output is correct
5 Correct 121 ms 13888 KB Output is correct
6 Correct 91 ms 13780 KB Output is correct
7 Correct 107 ms 13780 KB Output is correct
8 Correct 102 ms 13772 KB Output is correct
9 Correct 103 ms 13900 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3968 KB Output is correct
2 Correct 17 ms 4472 KB Output is correct
3 Correct 106 ms 8740 KB Output is correct
4 Correct 136 ms 10272 KB Output is correct
5 Correct 244 ms 10284 KB Output is correct
6 Correct 126 ms 10164 KB Output is correct
7 Correct 134 ms 10168 KB Output is correct
8 Correct 129 ms 10212 KB Output is correct
9 Correct 135 ms 10164 KB Output is correct
10 Correct 228 ms 10232 KB Output is correct
11 Correct 224 ms 10440 KB Output is correct
12 Correct 145 ms 11144 KB Output is correct
13 Correct 154 ms 10968 KB Output is correct
14 Correct 146 ms 11052 KB Output is correct
15 Correct 120 ms 10108 KB Output is correct
16 Correct 240 ms 10116 KB Output is correct
17 Correct 132 ms 10856 KB Output is correct
18 Correct 129 ms 10908 KB Output is correct
19 Correct 123 ms 10104 KB Output is correct
20 Correct 139 ms 11400 KB Output is correct
21 Correct 209 ms 10384 KB Output is correct
22 Correct 216 ms 10268 KB Output is correct
23 Correct 107 ms 10296 KB Output is correct
24 Correct 113 ms 10760 KB Output is correct
25 Correct 156 ms 13396 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 18552 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 27 ms 19192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -