oj.uz

Submission #415466

# Submission time Handle Problem Language Result Execution time Memory
415466 2021-06-01T06:26:39 Z 2qbingxuan Highway Tolls (IOI18_highway) C++14
100 / 100
 394 ms 12196 KB 
#include "highway.h"
#include <bits/stdc++.h>
#ifdef local
#define debug(x...) qqbx(#x, x)
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\e[1;32m(" << s << ") = ("), ... , (std::cerr << a << (--cnt ? ", " : "\e[0m)\n")));
}
#define pary(x...) danb(#x, x)
template <typename T> void danb(const char *s, T L, T R) {
    std::cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        std::cerr << (f++ ? ", " : "") << *L;
    std::cerr << " ]\e[0m\n";
}
#else
#define debug(...) ((void)0)
#define pary(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)

using namespace std;
using ll = long long;
const int maxn = 100025;
vector<pair<int,int>> g[maxn];
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    int M = U.size();
    for (int i = 0; i < M; i++) {
        g[U[i]].emplace_back(V[i], i);
        g[V[i]].emplace_back(U[i], i);
    }

    auto bfs = [&](int src) -> pair<vector<int>,vector<int>> {
        vector<int> dis(N, -1);
        vector<int> prv(N, -1);
        queue<int> q;
        dis[src] = 0, q.push(src);
        while (!q.empty()) {
            int i = q.front(); q.pop();
            for (auto [j, id]: g[i])
                if (dis[j] == -1)
                    prv[j] = id, dis[j] = dis[i] + 1, q.push(j);
        }
        return { prv, dis };
    };
    ll org = ask(vector<int>(M, 0));
    int pref = 0;
    for (int s = 1 << 20; s; s >>= 1) {
        if (pref+s >= M) continue;
        vector<int> tmp(M);
        for (int i = 0; i < M; i++) tmp[i] = (i < pref+s);
        if (ask(tmp) == org) {
            pref += s;
        }
    }
    assert(pref < M);
    auto [p1, d1] = bfs(U[pref]);
    auto [p2, d2] = bfs(V[pref]);
    debug(U[pref], V[pref]);
    pary(all(d1));
    pary(all(d2));

    vector<int> t1, t2;
    vector<int> span_tree(M, 1);
    span_tree[pref] = 0;
    for (int i = 0; i < N; i++)
        if (d1[i] != d2[i]) {
            if (i == U[pref] || i == V[pref]) continue;
            if (d1[i] < d2[i]) {
                span_tree[p1[i]] = 0;
                t1.push_back(i);
            } else {
                span_tree[p2[i]] = 0;
                t2.push_back(i);
            }
        }
    pary(all(span_tree));
    // assert(ask(span_tree) == org);

    sort(all(t1), [&](int u, int v){ return d1[u] > d1[v]; });
    sort(all(t2), [&](int u, int v){ return d2[u] > d2[v]; });

    pary(all(t1));
    pary(all(t2));

    int Sid = 0;
    for (int s = 1 << 20; s; s >>= 1) {
        if (Sid + s > t1.size()) continue;
        auto tmp = span_tree;
        for (int i = 0; i < t1.size(); i++) if (i < Sid + s) tmp[p1[t1[i]]] = 1;
        if (ask(tmp) == org) {
            Sid += s;
        }
    }
    int S = Sid < t1.size() ? t1[Sid] : U[pref];
    int Tid = 0;
    for (int s = 1 << 20; s; s >>= 1) {
        if (Tid + s > t2.size()) continue;
        auto tmp = span_tree;
        for (int i = 0; i < t2.size(); i++) if (i < Tid + s) tmp[p2[t2[i]]] = 1;
        if (ask(tmp) == org) {
            Tid += s;
        }
    }
    int T = Tid < t2.size() ? t2[Tid] : V[pref];
    answer(S, T);
    debug(S, T);
    debug(A, B);
}

Compilation message

highway.cpp: In lambda function:
highway.cpp:40:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |             for (auto [j, id]: g[i])
      |                       ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:57:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |     auto [p1, d1] = bfs(U[pref]);
      |          ^
highway.cpp:58:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |     auto [p2, d2] = bfs(V[pref]);
      |          ^
highway.cpp:88:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         if (Sid + s > t1.size()) continue;
      |             ~~~~~~~~^~~~~~~~~~~
highway.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for (int i = 0; i < t1.size(); i++) if (i < Sid + s) tmp[p1[t1[i]]] = 1;
      |                         ~~^~~~~~~~~~~
highway.cpp:95:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     int S = Sid < t1.size() ? t1[Sid] : U[pref];
      |             ~~~~^~~~~~~~~~~
highway.cpp:98:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         if (Tid + s > t2.size()) continue;
      |             ~~~~~~~~^~~~~~~~~~~
highway.cpp:100:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for (int i = 0; i < t2.size(); i++) if (i < Tid + s) tmp[p2[t2[i]]] = 1;
      |                         ~~^~~~~~~~~~~
highway.cpp:105:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     int T = Tid < t2.size() ? t2[Tid] : V[pref];
      |             ~~~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2632 KB Output is correct
2 Correct 17 ms 3468 KB Output is correct
3 Correct 250 ms 10276 KB Output is correct
4 Correct 247 ms 10180 KB Output is correct
5 Correct 165 ms 10184 KB Output is correct
6 Correct 177 ms 10240 KB Output is correct
7 Correct 247 ms 10232 KB Output is correct
8 Correct 264 ms 10320 KB Output is correct
9 Correct 165 ms 10188 KB Output is correct
10 Correct 210 ms 10192 KB Output is correct
11 Correct 186 ms 9696 KB Output is correct
12 Correct 239 ms 9696 KB Output is correct
13 Correct 178 ms 9704 KB Output is correct
14 Correct 202 ms 9664 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3400 KB Output is correct
2 Correct 46 ms 4160 KB Output is correct
3 Correct 35 ms 4972 KB Output is correct
4 Correct 120 ms 9756 KB Output is correct
5 Correct 179 ms 9752 KB Output is correct
6 Correct 207 ms 9648 KB Output is correct
7 Correct 194 ms 9684 KB Output is correct
8 Correct 182 ms 9720 KB Output is correct
9 Correct 227 ms 9604 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2728 KB Output is correct
2 Correct 26 ms 3480 KB Output is correct
3 Correct 114 ms 8588 KB Output is correct
4 Correct 259 ms 10180 KB Output is correct
5 Correct 236 ms 10176 KB Output is correct
6 Correct 246 ms 10272 KB Output is correct
7 Correct 142 ms 10192 KB Output is correct
8 Correct 149 ms 10256 KB Output is correct
9 Correct 174 ms 10260 KB Output is correct
10 Correct 262 ms 10288 KB Output is correct
11 Correct 177 ms 9676 KB Output is correct
12 Correct 185 ms 9740 KB Output is correct
13 Correct 239 ms 9704 KB Output is correct
14 Correct 192 ms 9588 KB Output is correct
15 Correct 243 ms 10196 KB Output is correct
16 Correct 230 ms 10208 KB Output is correct
17 Correct 266 ms 9664 KB Output is correct
18 Correct 283 ms 9676 KB Output is correct
19 Correct 192 ms 10256 KB Output is correct
20 Correct 195 ms 9800 KB Output is correct
21 Correct 226 ms 10432 KB Output is correct
22 Correct 213 ms 10432 KB Output is correct
23 Correct 149 ms 10240 KB Output is correct
24 Correct 135 ms 10328 KB Output is correct
25 Correct 269 ms 9888 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 3516 KB Output is correct
2 Correct 33 ms 3524 KB Output is correct
3 Correct 189 ms 10640 KB Output is correct
4 Correct 339 ms 11032 KB Output is correct
5 Correct 298 ms 12020 KB Output is correct
6 Correct 394 ms 12036 KB Output is correct
7 Correct 219 ms 11944 KB Output is correct
8 Correct 221 ms 12072 KB Output is correct
9 Correct 205 ms 9452 KB Output is correct
10 Correct 210 ms 9820 KB Output is correct
11 Correct 194 ms 10468 KB Output is correct
12 Correct 204 ms 11464 KB Output is correct
13 Correct 310 ms 11952 KB Output is correct
14 Correct 245 ms 12068 KB Output is correct
15 Correct 344 ms 12156 KB Output is correct
16 Correct 230 ms 10516 KB Output is correct
17 Correct 238 ms 10836 KB Output is correct
18 Correct 185 ms 10640 KB Output is correct
19 Correct 141 ms 10916 KB Output is correct
20 Correct 238 ms 11008 KB Output is correct
21 Correct 328 ms 12156 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3528 KB Output is correct
2 Correct 33 ms 3520 KB Output is correct
3 Correct 275 ms 10652 KB Output is correct
4 Correct 200 ms 10748 KB Output is correct
5 Correct 303 ms 11012 KB Output is correct
6 Correct 349 ms 12000 KB Output is correct
7 Correct 242 ms 10688 KB Output is correct
8 Correct 174 ms 10964 KB Output is correct
9 Correct 262 ms 11060 KB Output is correct
10 Correct 271 ms 12148 KB Output is correct
11 Correct 224 ms 12140 KB Output is correct
12 Correct 312 ms 12008 KB Output is correct
13 Correct 155 ms 10468 KB Output is correct
14 Correct 164 ms 9804 KB Output is correct
15 Correct 233 ms 10460 KB Output is correct
16 Correct 156 ms 9808 KB Output is correct
17 Correct 260 ms 10592 KB Output is correct
18 Correct 303 ms 9872 KB Output is correct
19 Correct 229 ms 11432 KB Output is correct
20 Correct 348 ms 11772 KB Output is correct
21 Correct 262 ms 12092 KB Output is correct
22 Correct 369 ms 12020 KB Output is correct
23 Correct 230 ms 12136 KB Output is correct
24 Correct 227 ms 12160 KB Output is correct
25 Correct 386 ms 12180 KB Output is correct
26 Correct 238 ms 12080 KB Output is correct
27 Correct 146 ms 10944 KB Output is correct
28 Correct 244 ms 10844 KB Output is correct
29 Correct 243 ms 10740 KB Output is correct
30 Correct 249 ms 10964 KB Output is correct
31 Correct 264 ms 10956 KB Output is correct
32 Correct 228 ms 10824 KB Output is correct
33 Correct 251 ms 11064 KB Output is correct
34 Correct 138 ms 10904 KB Output is correct
35 Correct 259 ms 10896 KB Output is correct
36 Correct 207 ms 10964 KB Output is correct
37 Correct 140 ms 11032 KB Output is correct
38 Correct 272 ms 10952 KB Output is correct
39 Correct 264 ms 12160 KB Output is correct
40 Correct 342 ms 12196 KB Output is correct
41 Correct 237 ms 12128 KB Output is correct
42 Correct 380 ms 12124 KB Output is correct