oj.uz

Submission #333429

# Submission time Handle Problem Language Result Execution time Memory
333429 2020-12-05T23:02:34 Z SHZhang Highway Tolls (IOI18_highway) C++14
90 / 100
 315 ms 12840 KB 
#include <cstdio>
#include <utility>
#include <vector>
#include <queue>
#include "highway.h"

using namespace std;

#define ll long long

vector<pair<int, int> > graph[150000];

int n, m; ll mindis;

void bfs(int node, vector<pair<int, int> >& seq)
{
    queue<int> que; que.push(node);
    vector<int> dist(n);
    for (int i = 0; i < n; i++) dist[i] = 100000000;
    dist[node] = 0;
    seq.push_back(make_pair(node, -1));
    while (!que.empty()) {
        int cur = que.front(); que.pop();
        for (int i = 0; i < graph[cur].size(); i++) {
            int nxt = graph[cur][i].first;
            if (dist[cur] + 1 < dist[nxt]) {
                dist[nxt] = dist[cur] + 1;
                que.push(nxt); seq.push_back(make_pair(nxt, graph[cur][i].second));
            }
        }
    }
}

int binary_search(vector<pair<int, int> >& seq)
{
    int l = 0; int r = n - 1;
    while (l < r) {
        vector<int> wt(m);
        for (int i = 0; i < m; i++) wt[i] = 1;
        int mid = (l + r) / 2;
        for (int i = 1; i <= mid; i++) {
            wt[seq[i].second] = 0;
        }
        ll dis = ask(wt);
        if (dis == mindis) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return seq[l].first;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    n = N; m = U.size();
    for (int i = 0; i < m; i++) {
        graph[U[i]].push_back(make_pair(V[i], i));
        graph[V[i]].push_back(make_pair(U[i], i));
    }
    int l = 0; int r = n - 1;
    vector<int> wt(m);
    for (int i = 0; i < m; i++) wt[i] = 0;
    mindis = ask(wt);
    //fprintf(stderr, "here1");
    while (l < r) {
        vector<int> wt(m);
        for (int i = 0; i < m; i++) wt[i] = 0;
        int mid = (l + r) / 2;
        for (int i = 0; i <= mid; i++) {
            for (int j = 0; j < graph[i].size(); j++) {
                wt[graph[i][j].second] = 1;
            }
        }
        ll dis = ask(wt);
        if (dis == mindis) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    //fprintf(stderr, "here");
    int midnode = l;
    vector<pair<int, int> > seq; bfs(midnode, seq);
    int S = binary_search(seq);
    seq.clear();
    bfs(S, seq);
    int T = binary_search(seq);
    answer(S, T);
}

Compilation message

highway.cpp: In function 'void bfs(int, std::vector<std::pair<int, int> >&)':
highway.cpp:24:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for (int i = 0; i < graph[cur].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:70:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             for (int j = 0; j < graph[i].size(); j++) {
      |                             ~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3948 KB Output is correct
2 Correct 18 ms 4588 KB Output is correct
3 Correct 173 ms 10908 KB Output is correct
4 Correct 181 ms 10912 KB Output is correct
5 Correct 193 ms 11036 KB Output is correct
6 Correct 180 ms 10904 KB Output is correct
7 Correct 177 ms 10908 KB Output is correct
8 Correct 174 ms 11020 KB Output is correct
9 Correct 171 ms 11096 KB Output is correct
10 Correct 181 ms 10820 KB Output is correct
11 Correct 188 ms 10296 KB Output is correct
12 Correct 189 ms 10272 KB Output is correct
13 Correct 195 ms 10312 KB Output is correct
14 Correct 181 ms 10364 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4588 KB Output is correct
2 Correct 29 ms 5288 KB Output is correct
3 Correct 57 ms 5896 KB Output is correct
4 Correct 173 ms 10268 KB Output is correct
5 Correct 126 ms 10288 KB Output is correct
6 Correct 173 ms 10316 KB Output is correct
7 Correct 184 ms 10292 KB Output is correct
8 Correct 195 ms 10288 KB Output is correct
9 Correct 130 ms 10264 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3944 KB Output is correct
2 Correct 22 ms 4588 KB Output is correct
3 Correct 162 ms 9356 KB Output is correct
4 Correct 223 ms 10868 KB Output is correct
5 Correct 202 ms 10828 KB Output is correct
6 Correct 180 ms 10884 KB Output is correct
7 Correct 178 ms 10880 KB Output is correct
8 Correct 169 ms 10880 KB Output is correct
9 Correct 177 ms 10872 KB Output is correct
10 Correct 176 ms 10876 KB Output is correct
11 Correct 190 ms 10276 KB Output is correct
12 Correct 185 ms 10400 KB Output is correct
13 Correct 231 ms 10464 KB Output is correct
14 Correct 230 ms 10280 KB Output is correct
15 Correct 199 ms 10896 KB Output is correct
16 Correct 177 ms 10920 KB Output is correct
17 Correct 171 ms 10272 KB Output is correct
18 Correct 224 ms 10364 KB Output is correct
19 Correct 173 ms 10884 KB Output is correct
20 Correct 201 ms 10268 KB Output is correct
21 Correct 203 ms 11216 KB Output is correct
22 Correct 195 ms 11140 KB Output is correct
23 Correct 154 ms 11164 KB Output is correct
24 Correct 166 ms 11068 KB Output is correct
25 Correct 174 ms 10400 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4716 KB Output is correct
2 Correct 21 ms 4716 KB Output is correct
3 Correct 204 ms 11288 KB Output is correct
4 Correct 223 ms 11828 KB Output is correct
5 Correct 246 ms 12776 KB Output is correct
6 Correct 250 ms 12728 KB Output is correct
7 Correct 263 ms 12684 KB Output is correct
8 Correct 255 ms 12740 KB Output is correct
9 Correct 272 ms 10632 KB Output is correct
10 Correct 216 ms 10976 KB Output is correct
11 Correct 294 ms 10952 KB Output is correct
12 Correct 239 ms 12416 KB Output is correct
13 Correct 297 ms 12464 KB Output is correct
14 Correct 308 ms 12632 KB Output is correct
15 Correct 315 ms 12704 KB Output is correct
16 Correct 292 ms 11284 KB Output is correct
17 Correct 165 ms 11024 KB Output is correct
18 Correct 190 ms 11348 KB Output is correct
19 Correct 163 ms 11192 KB Output is correct
20 Correct 169 ms 11240 KB Output is correct
21 Correct 238 ms 12840 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4716 KB Output is correct
2 Correct 22 ms 4844 KB Output is correct
3 Partially correct 195 ms 11212 KB Output is partially correct
4 Correct 215 ms 11496 KB Output is correct
5 Partially correct 297 ms 11616 KB Output is partially correct
6 Correct 307 ms 12636 KB Output is correct
7 Partially correct 197 ms 11280 KB Output is partially correct
8 Correct 208 ms 11424 KB Output is correct
9 Partially correct 202 ms 11660 KB Output is partially correct
10 Correct 238 ms 12732 KB Output is correct
11 Partially correct 263 ms 12564 KB Output is partially correct
12 Partially correct 235 ms 12700 KB Output is partially correct
13 Correct 241 ms 10872 KB Output is correct
14 Correct 197 ms 10908 KB Output is correct
15 Correct 219 ms 10868 KB Output is correct
16 Correct 201 ms 10988 KB Output is correct
17 Correct 254 ms 11004 KB Output is correct
18 Correct 195 ms 11060 KB Output is correct
19 Correct 232 ms 12316 KB Output is correct
20 Partially correct 229 ms 12480 KB Output is partially correct
21 Correct 261 ms 12748 KB Output is correct
22 Correct 286 ms 12600 KB Output is correct
23 Partially correct 264 ms 12620 KB Output is partially correct
24 Partially correct 253 ms 12648 KB Output is partially correct
25 Partially correct 294 ms 12636 KB Output is partially correct
26 Partially correct 234 ms 12560 KB Output is partially correct
27 Correct 173 ms 11248 KB Output is correct
28 Partially correct 169 ms 11108 KB Output is partially correct
29 Partially correct 169 ms 11336 KB Output is partially correct
30 Correct 186 ms 11260 KB Output is correct
31 Correct 159 ms 11176 KB Output is correct
32 Partially correct 186 ms 11040 KB Output is partially correct
33 Correct 175 ms 11404 KB Output is correct
34 Correct 165 ms 11096 KB Output is correct
35 Correct 155 ms 11276 KB Output is correct
36 Partially correct 164 ms 11016 KB Output is partially correct
37 Correct 191 ms 11464 KB Output is correct
38 Partially correct 218 ms 11260 KB Output is partially correct
39 Partially correct 236 ms 12764 KB Output is partially correct
40 Partially correct 236 ms 12732 KB Output is partially correct
41 Correct 247 ms 12608 KB Output is correct
42 Partially correct 231 ms 12708 KB Output is partially correct