oj.uz

Submission #466853

# Submission time Handle Problem Language Result Execution time Memory
466853 2021-08-20T20:56:11 Z luciocf Highway Tolls (IOI18_highway) C++14
100 / 100
 384 ms 33780 KB 
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;

const int maxn = 2e5+10;

typedef pair<int, int> pii;
typedef long long ll;

int M;
ll D;

vector<pii> grafo[maxn], tree[2][maxn];

int pai[2][maxn], edge[2][maxn];
int dist[2][maxn];

bool is[maxn];

void bfs(int s, int k)
{
    queue<int> fila;
    dist[k][s] = 0, fila.push(s);

    while (!fila.empty())
    {
        int u = fila.front(); fila.pop();

        for (auto pp: grafo[u])
        {
            int v = pp.first, e = pp.second;

            if (dist[k][v] == -1)
            {
                dist[k][v] = dist[k][u]+1, pai[k][v] = u, edge[k][v] = e;
                fila.push(v);
            }
        }
    }
}

vector<int> lista[2];

void dfs(int u, int p, int k)
{
    for (auto pp: tree[k][u])
        if (pp.first != p)
            dfs(pp.first, u, k);

    lista[k].push_back(u);
}

int get(int k)
{
    int ini = 0, fim = (int)(lista[k].size())-2, ans = lista[k].back();

    while (ini <= fim)
    {
        int mid = (ini+fim)>>1;

        vector<int> w(M, 1);

        for (int i = 0; i < M; i++)
            if (is[i])
                w[i] = 0;

        for (int i = 0; i <= mid; i++)
            w[edge[k][lista[k][i]]] = 1;

        ll d = ask(w);

        if (d > D) ans = lista[k][mid], fim = mid-1;
        else ini = mid+1;
    }

    return ans;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
    M = U.size();
    vector<int> w(M);

    D = ask(w);

    int ini = 0, fim = M-1, ind = 0;
    while (ini <= fim)
    {
        int mid = (ini+fim)>>1;

        for (int i = 0; i <= mid; i++)
            w[i] = 1;

        ll d = ask(w);

        if (d > D) ind = mid, fim = mid-1;
        else ini = mid+1;

        for (int i = 0; i <= mid; i++)
            w[i] = 0;
    }

    for (int i = 0; i < M; i++)
    {
        grafo[U[i]].push_back({V[i], i});
        grafo[V[i]].push_back({U[i], i});
    }

    memset(dist, -1, sizeof dist);
    bfs(U[ind], 0); bfs(V[ind], 1);

    is[ind] = 1;

    for (int i = 0; i < N; i++)
    {
        if (dist[0][i] == dist[1][i] || i == U[ind] || i == V[ind]) continue;

        if (dist[0][i] < dist[1][i])
        {
            is[edge[0][i]] = 1;

            tree[1][i].push_back({pai[0][i], edge[0][i]});
            tree[0][pai[0][i]].push_back({i, edge[0][i]});
        }
        else
        {
            is[edge[1][i]] = 1;

            tree[1][i].push_back({pai[1][i], edge[1][i]});
            tree[1][pai[1][i]].push_back({i, edge[1][i]});
        }
    }

    dfs(U[ind], -1, 0); dfs(V[ind], -1, 1);

    answer(get(0), get(1));
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15944 KB Output is correct
2 Correct 10 ms 15928 KB Output is correct
3 Correct 10 ms 15880 KB Output is correct
4 Correct 10 ms 15928 KB Output is correct
5 Correct 11 ms 15924 KB Output is correct
6 Correct 10 ms 15944 KB Output is correct
7 Correct 11 ms 15944 KB Output is correct
8 Correct 10 ms 15944 KB Output is correct
9 Correct 10 ms 15944 KB Output is correct
10 Correct 10 ms 15944 KB Output is correct
11 Correct 10 ms 15908 KB Output is correct
12 Correct 10 ms 15944 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16068 KB Output is correct
2 Correct 26 ms 17224 KB Output is correct
3 Correct 181 ms 27868 KB Output is correct
4 Correct 186 ms 26820 KB Output is correct
5 Correct 179 ms 26764 KB Output is correct
6 Correct 200 ms 26764 KB Output is correct
7 Correct 181 ms 26796 KB Output is correct
8 Correct 218 ms 26844 KB Output is correct
9 Correct 172 ms 27828 KB Output is correct
10 Correct 201 ms 26796 KB Output is correct
11 Correct 213 ms 28444 KB Output is correct
12 Correct 234 ms 29736 KB Output is correct
13 Correct 190 ms 27240 KB Output is correct
14 Correct 205 ms 29752 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17608 KB Output is correct
2 Correct 44 ms 19288 KB Output is correct
3 Correct 58 ms 21836 KB Output is correct
4 Correct 133 ms 30144 KB Output is correct
5 Correct 197 ms 30284 KB Output is correct
6 Correct 128 ms 30868 KB Output is correct
7 Correct 155 ms 33780 KB Output is correct
8 Correct 132 ms 30620 KB Output is correct
9 Correct 188 ms 31996 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16072 KB Output is correct
2 Correct 29 ms 17264 KB Output is correct
3 Correct 165 ms 24340 KB Output is correct
4 Correct 206 ms 26800 KB Output is correct
5 Correct 178 ms 27920 KB Output is correct
6 Correct 156 ms 26796 KB Output is correct
7 Correct 227 ms 27952 KB Output is correct
8 Correct 171 ms 27828 KB Output is correct
9 Correct 177 ms 27820 KB Output is correct
10 Correct 209 ms 27880 KB Output is correct
11 Correct 218 ms 29592 KB Output is correct
12 Correct 185 ms 28012 KB Output is correct
13 Correct 260 ms 29516 KB Output is correct
14 Correct 246 ms 28948 KB Output is correct
15 Correct 209 ms 26860 KB Output is correct
16 Correct 219 ms 26764 KB Output is correct
17 Correct 239 ms 29432 KB Output is correct
18 Correct 197 ms 29964 KB Output is correct
19 Correct 180 ms 27828 KB Output is correct
20 Correct 224 ms 28012 KB Output is correct
21 Correct 144 ms 27164 KB Output is correct
22 Correct 148 ms 27144 KB Output is correct
23 Correct 158 ms 27324 KB Output is correct
24 Correct 186 ms 27680 KB Output is correct
25 Correct 212 ms 33032 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 17196 KB Output is correct
2 Correct 33 ms 17344 KB Output is correct
3 Correct 219 ms 27016 KB Output is correct
4 Correct 325 ms 27976 KB Output is correct
5 Correct 266 ms 28172 KB Output is correct
6 Correct 286 ms 28036 KB Output is correct
7 Correct 350 ms 27784 KB Output is correct
8 Correct 337 ms 27936 KB Output is correct
9 Correct 227 ms 23860 KB Output is correct
10 Correct 235 ms 24036 KB Output is correct
11 Correct 192 ms 25200 KB Output is correct
12 Correct 324 ms 26392 KB Output is correct
13 Correct 265 ms 27144 KB Output is correct
14 Correct 297 ms 27964 KB Output is correct
15 Correct 283 ms 28776 KB Output is correct
16 Correct 273 ms 24588 KB Output is correct
17 Correct 158 ms 27276 KB Output is correct
18 Correct 150 ms 27632 KB Output is correct
19 Correct 138 ms 27404 KB Output is correct
20 Correct 214 ms 27516 KB Output is correct
21 Correct 340 ms 28848 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 17268 KB Output is correct
2 Correct 32 ms 17352 KB Output is correct
3 Correct 261 ms 26952 KB Output is correct
4 Correct 239 ms 27084 KB Output is correct
5 Correct 247 ms 27216 KB Output is correct
6 Correct 277 ms 28004 KB Output is correct
7 Correct 239 ms 27180 KB Output is correct
8 Correct 282 ms 27196 KB Output is correct
9 Correct 227 ms 27268 KB Output is correct
10 Correct 337 ms 27904 KB Output is correct
11 Correct 329 ms 27916 KB Output is correct
12 Correct 306 ms 27992 KB Output is correct
13 Correct 201 ms 25208 KB Output is correct
14 Correct 188 ms 24028 KB Output is correct
15 Correct 248 ms 25188 KB Output is correct
16 Correct 239 ms 24016 KB Output is correct
17 Correct 244 ms 25188 KB Output is correct
18 Correct 174 ms 24044 KB Output is correct
19 Correct 332 ms 26508 KB Output is correct
20 Correct 273 ms 28008 KB Output is correct
21 Correct 305 ms 27952 KB Output is correct
22 Correct 342 ms 27972 KB Output is correct
23 Correct 295 ms 28032 KB Output is correct
24 Correct 343 ms 28060 KB Output is correct
25 Correct 278 ms 28492 KB Output is correct
26 Correct 299 ms 28484 KB Output is correct
27 Correct 169 ms 27452 KB Output is correct
28 Correct 171 ms 27336 KB Output is correct
29 Correct 178 ms 27784 KB Output is correct
30 Correct 205 ms 27464 KB Output is correct
31 Correct 160 ms 27464 KB Output is correct
32 Correct 165 ms 27204 KB Output is correct
33 Correct 165 ms 27664 KB Output is correct
34 Correct 205 ms 27404 KB Output is correct
35 Correct 190 ms 27316 KB Output is correct
36 Correct 144 ms 27160 KB Output is correct
37 Correct 176 ms 27592 KB Output is correct
38 Correct 171 ms 27412 KB Output is correct
39 Correct 298 ms 29264 KB Output is correct
40 Correct 272 ms 30388 KB Output is correct
41 Correct 307 ms 28560 KB Output is correct
42 Correct 384 ms 29480 KB Output is correct