oj.uz

Submission #720986

# Submission time Handle Problem Language Result Execution time Memory
720986 2023-04-10T01:59:32 Z LittleCube Highway Tolls (IOI18_highway) C++14
100 / 100
 235 ms 12060 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
using namespace std;

namespace
{
    int N, M, u, v;
    ll D;
    vector<pii> E[90000];
    int vis[90000], par[90000], dis[90000];
};

void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
    ::N = N;
    ::M = U.size();
    D = ask(vector<int>(M, 0));
    int e = 0;
    {
        int L = 0, R = M - 1;
        while (L < R)
        {
            int mid = (L + R) / 2;
            vector<int> state(M, 0);
            for (int i = 0; i <= mid; i++)
                state[i] = 1;
            if (ask(state) > D)
                R = mid;
            else
                L = mid + 1;
        }
        u = U[L], v = V[L];
        e = L;
    }
    cerr << u << ' ' << v << '\n';
    for (int i = 0; i < M; i++)
        if (i != e)
            E[U[i]].emplace_back(pii(V[i], i)), E[V[i]].emplace_back(pii(U[i], i));

    vector<int> s = {u}, t = {v}, ontree(M, 1);
    ontree[e] = 0;
    queue<int> q;
    vis[u] = 1, vis[v] = 2;
    q.push(u);
    q.push(v);
    while (!q.empty())
    {
        auto i = q.front();
        q.pop();
        for (auto [j, k] : E[i])
            if(!vis[j])
            {
                vis[j] = vis[i];
                (vis[j] == 1 ? s : t).emplace_back(j);
                ontree[par[j] = k] = 0;
                dis[j] = dis[i] + 1;
                
                q.push(j);
            }
    }
    auto find = [&](vector<int> S)
    {
        sort(S.begin(), S.end(), [&](int i, int j)
             { return dis[i] < dis[j]; });
        int L = 0, R = S.size() - 1;
        while(L < R)
        {
            int mid = (L + R) / 2;
            vector<int> state = ontree;
            for (int i = mid + 1; i < S.size(); i++)
                state[par[S[i]]] = 1;
            if(ask(state) > D)
                L = mid + 1;
            else
                R = mid;
        }
        return S[L];
    };
    answer(find(s), find(t));
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:54:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |         for (auto [j, k] : E[i])
      |                   ^
highway.cpp: In lambda function:
highway.cpp:74:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             for (int i = mid + 1; i < S.size(); i++)
      |                                   ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 13 ms 3152 KB Output is correct
3 Correct 124 ms 9716 KB Output is correct
4 Correct 139 ms 9800 KB Output is correct
5 Correct 125 ms 9840 KB Output is correct
6 Correct 102 ms 9708 KB Output is correct
7 Correct 112 ms 9828 KB Output is correct
8 Correct 142 ms 9824 KB Output is correct
9 Correct 187 ms 9724 KB Output is correct
10 Correct 122 ms 9752 KB Output is correct
11 Correct 169 ms 9268 KB Output is correct
12 Correct 126 ms 9168 KB Output is correct
13 Correct 125 ms 9156 KB Output is correct
14 Correct 117 ms 9180 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3132 KB Output is correct
2 Correct 22 ms 3956 KB Output is correct
3 Correct 42 ms 4772 KB Output is correct
4 Correct 86 ms 9244 KB Output is correct
5 Correct 92 ms 9244 KB Output is correct
6 Correct 107 ms 9324 KB Output is correct
7 Correct 92 ms 9212 KB Output is correct
8 Correct 124 ms 9296 KB Output is correct
9 Correct 89 ms 9160 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2512 KB Output is correct
2 Correct 18 ms 3256 KB Output is correct
3 Correct 113 ms 8112 KB Output is correct
4 Correct 110 ms 9700 KB Output is correct
5 Correct 176 ms 9764 KB Output is correct
6 Correct 132 ms 9812 KB Output is correct
7 Correct 114 ms 9832 KB Output is correct
8 Correct 110 ms 9800 KB Output is correct
9 Correct 151 ms 9712 KB Output is correct
10 Correct 130 ms 9732 KB Output is correct
11 Correct 111 ms 9172 KB Output is correct
12 Correct 123 ms 9272 KB Output is correct
13 Correct 122 ms 9360 KB Output is correct
14 Correct 122 ms 9260 KB Output is correct
15 Correct 112 ms 9724 KB Output is correct
16 Correct 117 ms 9832 KB Output is correct
17 Correct 123 ms 9176 KB Output is correct
18 Correct 137 ms 9252 KB Output is correct
19 Correct 124 ms 9720 KB Output is correct
20 Correct 117 ms 9136 KB Output is correct
21 Correct 96 ms 10368 KB Output is correct
22 Correct 96 ms 10360 KB Output is correct
23 Correct 105 ms 10212 KB Output is correct
24 Correct 113 ms 10168 KB Output is correct
25 Correct 111 ms 9388 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3412 KB Output is correct
2 Correct 21 ms 3272 KB Output is correct
3 Correct 128 ms 10132 KB Output is correct
4 Correct 159 ms 10704 KB Output is correct
5 Correct 171 ms 11792 KB Output is correct
6 Correct 178 ms 11696 KB Output is correct
7 Correct 182 ms 12020 KB Output is correct
8 Correct 191 ms 11944 KB Output is correct
9 Correct 138 ms 9136 KB Output is correct
10 Correct 116 ms 9672 KB Output is correct
11 Correct 125 ms 10260 KB Output is correct
12 Correct 170 ms 11224 KB Output is correct
13 Correct 172 ms 11644 KB Output is correct
14 Correct 212 ms 11756 KB Output is correct
15 Correct 198 ms 11688 KB Output is correct
16 Correct 150 ms 10288 KB Output is correct
17 Correct 119 ms 10272 KB Output is correct
18 Correct 131 ms 10432 KB Output is correct
19 Correct 130 ms 10424 KB Output is correct
20 Correct 114 ms 10440 KB Output is correct
21 Correct 174 ms 11636 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3256 KB Output is correct
2 Correct 16 ms 3452 KB Output is correct
3 Correct 169 ms 10328 KB Output is correct
4 Correct 138 ms 10528 KB Output is correct
5 Correct 173 ms 10684 KB Output is correct
6 Correct 197 ms 11908 KB Output is correct
7 Correct 140 ms 10312 KB Output is correct
8 Correct 153 ms 10404 KB Output is correct
9 Correct 164 ms 10884 KB Output is correct
10 Correct 203 ms 11792 KB Output is correct
11 Correct 182 ms 11856 KB Output is correct
12 Correct 177 ms 11832 KB Output is correct
13 Correct 131 ms 10260 KB Output is correct
14 Correct 153 ms 9640 KB Output is correct
15 Correct 149 ms 10412 KB Output is correct
16 Correct 134 ms 9668 KB Output is correct
17 Correct 172 ms 10312 KB Output is correct
18 Correct 183 ms 9688 KB Output is correct
19 Correct 189 ms 11288 KB Output is correct
20 Correct 165 ms 11472 KB Output is correct
21 Correct 220 ms 12060 KB Output is correct
22 Correct 223 ms 11824 KB Output is correct
23 Correct 176 ms 11820 KB Output is correct
24 Correct 178 ms 11928 KB Output is correct
25 Correct 176 ms 11752 KB Output is correct
26 Correct 189 ms 11776 KB Output is correct
27 Correct 154 ms 10368 KB Output is correct
28 Correct 114 ms 10272 KB Output is correct
29 Correct 141 ms 10544 KB Output is correct
30 Correct 108 ms 10392 KB Output is correct
31 Correct 107 ms 10452 KB Output is correct
32 Correct 103 ms 10352 KB Output is correct
33 Correct 134 ms 10504 KB Output is correct
34 Correct 105 ms 10304 KB Output is correct
35 Correct 118 ms 10360 KB Output is correct
36 Correct 125 ms 10224 KB Output is correct
37 Correct 129 ms 10440 KB Output is correct
38 Correct 106 ms 10424 KB Output is correct
39 Correct 196 ms 11872 KB Output is correct
40 Correct 216 ms 11796 KB Output is correct
41 Correct 235 ms 11720 KB Output is correct
42 Correct 220 ms 11884 KB Output is correct