oj.uz

Submission #1014988

# Submission time Handle Problem Language Result Execution time Memory
1014988 2024-07-05T21:52:22 Z ThegeekKnight16 Highway Tolls (IOI18_highway) C++17
90 / 100
 167 ms 10852 KB 
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long ll;
vector<vector<pair<int, int>>> grafo;
vector<int> Marc;

// long long ask(vector<int> w);

int findNode(int S, vector<int> &w, int matters, ll dist)
{
    queue<int> q; vector<int> poss;
    Marc[S] = 1; q.push(S);
    // w[matters] = 1;
    while (!q.empty())
    {
        int cur = q.front(); q.pop();
        poss.push_back(cur);

        for (auto [viz, id] : grafo[cur])
        {
            if (Marc[viz] || w[id]) continue;
            Marc[viz] = 1; q.push(viz);
        }
    }
    // w[matters] = 0;

    int id = 0;
    for (int k = 16; k >= 0; k--)
    {
        int m = id | (1 << k);
        if (m >= poss.size()) continue;
        for (int v = 0; v < min(m, (int)poss.size()); v++)
            for (auto [viz, id] : grafo[poss[v]])
                w[id] = 0;

        for (int v = m; v < poss.size(); v++)
            for (auto [viz, id] : grafo[poss[v]])
                w[id] = 1;

        for (int i = matters+1; i < w.size(); i++) w[i] = 1;
        if (ask(w) != dist) id |= (1 << k);
    }

    return poss[id];
}

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

    int matters = 0;
    for (int k = 16; k >= 0; k--)
    {
        int m = matters | (1 << k);
        if (m >= M) continue;
        for (int i = 0; i < min(m, M); i++) w[i] = 0;
        for (int i = m; i < M; i++) w[i] = 1;
        if (ask(w) != dist) matters |= (1 << k);
    }

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

    grafo.resize(N); Marc.resize(N, 0);
    for (int i = 0; i < M; i++)
    {
        grafo[U[i]].emplace_back(V[i], i);
        grafo[V[i]].emplace_back(U[i], i);
    }
    // cerr << "matters: " << matters << ", (" << U[matters] << ", " << V[matters] << ") " << '\n';
    int S = findNode(U[matters], w, matters, dist);

    fill(Marc.begin(), Marc.end(), 0);
    for (int i = 0; i <= matters; i++) w[i] = 0;
    for (int i = matters+1; i < M; i++) w[i] = 1;

    int T = findNode(S, w, matters, dist);
    // cerr << "S: " << S << ", T: " << T << '\n';
    answer(S, T);
}

Compilation message

highway.cpp: In function 'int findNode(int, std::vector<int>&, int, ll)':
highway.cpp:32:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         if (m >= poss.size()) continue;
      |             ~~^~~~~~~~~~~~~~
highway.cpp:37:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for (int v = m; v < poss.size(); v++)
      |                         ~~^~~~~~~~~~~~~
highway.cpp:41:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int i = matters+1; i < w.size(); i++) w[i] = 1;
      |                                 ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 8 ms 1272 KB Output is correct
3 Correct 117 ms 8860 KB Output is correct
4 Correct 111 ms 8848 KB Output is correct
5 Correct 111 ms 8864 KB Output is correct
6 Correct 101 ms 8512 KB Output is correct
7 Correct 104 ms 8556 KB Output is correct
8 Correct 73 ms 8208 KB Output is correct
9 Correct 99 ms 8460 KB Output is correct
10 Correct 104 ms 8836 KB Output is correct
11 Correct 95 ms 8504 KB Output is correct
12 Correct 77 ms 7880 KB Output is correct
13 Correct 123 ms 8356 KB Output is correct
14 Correct 100 ms 8516 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1112 KB Output is correct
2 Correct 15 ms 2084 KB Output is correct
3 Correct 19 ms 3008 KB Output is correct
4 Correct 66 ms 7932 KB Output is correct
5 Correct 70 ms 7860 KB Output is correct
6 Correct 74 ms 8208 KB Output is correct
7 Correct 69 ms 8344 KB Output is correct
8 Correct 65 ms 7972 KB Output is correct
9 Correct 70 ms 8272 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 10 ms 1532 KB Output is correct
3 Correct 84 ms 6848 KB Output is correct
4 Correct 88 ms 8284 KB Output is correct
5 Correct 103 ms 8896 KB Output is correct
6 Correct 88 ms 8288 KB Output is correct
7 Correct 65 ms 7888 KB Output is correct
8 Correct 104 ms 8760 KB Output is correct
9 Correct 103 ms 8560 KB Output is correct
10 Correct 98 ms 8652 KB Output is correct
11 Correct 112 ms 8360 KB Output is correct
12 Correct 100 ms 8328 KB Output is correct
13 Correct 83 ms 7940 KB Output is correct
14 Correct 95 ms 7976 KB Output is correct
15 Correct 92 ms 8412 KB Output is correct
16 Correct 99 ms 8512 KB Output is correct
17 Correct 100 ms 8332 KB Output is correct
18 Correct 123 ms 8508 KB Output is correct
19 Correct 62 ms 8036 KB Output is correct
20 Correct 74 ms 7496 KB Output is correct
21 Correct 73 ms 8868 KB Output is correct
22 Correct 63 ms 9164 KB Output is correct
23 Correct 78 ms 9236 KB Output is correct
24 Correct 79 ms 9376 KB Output is correct
25 Correct 79 ms 8464 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1368 KB Output is correct
2 Correct 10 ms 1368 KB Output is correct
3 Correct 113 ms 10052 KB Output is correct
4 Correct 121 ms 9924 KB Output is correct
5 Correct 142 ms 10852 KB Output is correct
6 Correct 140 ms 10640 KB Output is correct
7 Correct 151 ms 10804 KB Output is correct
8 Correct 144 ms 10624 KB Output is correct
9 Correct 74 ms 6852 KB Output is correct
10 Correct 89 ms 7424 KB Output is correct
11 Correct 95 ms 8152 KB Output is correct
12 Correct 133 ms 9844 KB Output is correct
13 Correct 133 ms 10220 KB Output is correct
14 Correct 136 ms 10848 KB Output is correct
15 Correct 137 ms 10696 KB Output is correct
16 Correct 124 ms 8304 KB Output is correct
17 Correct 87 ms 9296 KB Output is correct
18 Correct 74 ms 9520 KB Output is correct
19 Correct 80 ms 9516 KB Output is correct
20 Correct 85 ms 9500 KB Output is correct
21 Correct 134 ms 10728 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1388 KB Output is correct
2 Correct 11 ms 1456 KB Output is correct
3 Partially correct 108 ms 9312 KB Output is partially correct
4 Correct 122 ms 9652 KB Output is correct
5 Correct 113 ms 9720 KB Output is correct
6 Partially correct 139 ms 10644 KB Output is partially correct
7 Partially correct 115 ms 9332 KB Output is partially correct
8 Partially correct 120 ms 9464 KB Output is partially correct
9 Partially correct 130 ms 9692 KB Output is partially correct
10 Partially correct 137 ms 10656 KB Output is partially correct
11 Partially correct 157 ms 10704 KB Output is partially correct
12 Partially correct 135 ms 10608 KB Output is partially correct
13 Correct 85 ms 7552 KB Output is correct
14 Correct 86 ms 7100 KB Output is correct
15 Correct 88 ms 7716 KB Output is correct
16 Correct 119 ms 7636 KB Output is correct
17 Correct 104 ms 8136 KB Output is correct
18 Correct 100 ms 7536 KB Output is correct
19 Correct 143 ms 9576 KB Output is correct
20 Partially correct 124 ms 10264 KB Output is partially correct
21 Partially correct 134 ms 10708 KB Output is partially correct
22 Partially correct 146 ms 10676 KB Output is partially correct
23 Partially correct 134 ms 10688 KB Output is partially correct
24 Partially correct 144 ms 10704 KB Output is partially correct
25 Partially correct 149 ms 10676 KB Output is partially correct
26 Partially correct 143 ms 10704 KB Output is partially correct
27 Correct 74 ms 8968 KB Output is correct
28 Correct 83 ms 9368 KB Output is correct
29 Correct 76 ms 8820 KB Output is correct
30 Partially correct 93 ms 9416 KB Output is partially correct
31 Partially correct 83 ms 9476 KB Output is partially correct
32 Correct 89 ms 9456 KB Output is correct
33 Correct 77 ms 9164 KB Output is correct
34 Correct 99 ms 9080 KB Output is correct
35 Correct 92 ms 9524 KB Output is correct
36 Correct 75 ms 8660 KB Output is correct
37 Correct 99 ms 9000 KB Output is correct
38 Correct 97 ms 8956 KB Output is correct
39 Partially correct 151 ms 10736 KB Output is partially correct
40 Partially correct 167 ms 10704 KB Output is partially correct
41 Correct 145 ms 10812 KB Output is correct
42 Partially correct 140 ms 10716 KB Output is partially correct