oj.uz

Submission #75117

# Submission time Handle Problem Language Result Execution time Memory
75117 2018-09-08T12:03:33 Z imeimi2000 Highway Tolls (IOI18_highway) C++17
100 / 100
 328 ms 9868 KB 
#include "highway.h"
#include <queue>
#include <algorithm>

using namespace std;
typedef long long llong;

int n, m;
vector<int> edge[90000];
int dist1[90000];
int dist2[90000];

void bfs(int dist[], int S) {
    for (int i = 0; i < n; ++i) dist[i] = n;
    queue<int> q;
    dist[S] = 0;
    q.push(S);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i : edge[x]) {
            if (dist[i] < n) continue;
            dist[i] = dist[x] + 1;
            q.push(i);
        }
    }
}

int ch[90000];
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    n = N;
    m = U.size();
    llong d;
    {
        vector<int> q(m, 0);
        d = ask(q);
    }
    
    int L, R;
    {
        int s = 0, e = m - 1;
        while (s < e) {
            int md = (s + e) / 2;
            vector<int> q(m, 0);
            for (int i = 0; i <= md; ++i) q[i] = 1;
            if (ask(q) != d) e = md;
            else s = md + 1;
        }
        L = U[s];
        R = V[s];
    }
    
    for (int i = 0; i < m; ++i) {
        edge[U[i]].push_back(V[i]);
        edge[V[i]].push_back(U[i]);
    }
    
    bfs(dist1, L); bfs(dist2, R);
    vector<int> LP, RP;
    for (int i = 0; i < n; ++i) {
        if (dist1[i] < dist2[i]) LP.push_back(i);
        if (dist1[i] > dist2[i]) RP.push_back(i);
    }
    
    sort(LP.begin(), LP.end(), [&](int i, int j) {
        return dist1[i] > dist1[j];
    });
    
    sort(RP.begin(), RP.end(), [&](int i, int j) {
        return dist2[i] > dist2[j];
    });
    
    {
        int s = 0, e = LP.size() - 1;
        while (s < e) {
            int md = (s + e) / 2;
            vector<int> q(m);
            for (int i = 0; i < n; ++i) ch[i] = 0;
            for (int i = 0; i <= md; ++i) ch[LP[i]] = 1;
            for (int i = 0; i < m; ++i) q[i] = ch[U[i]] ^ ch[V[i]];
            if (ask(q) != d) e = md;
            else s = md + 1;
        }
        L = LP[s];
    }
    
    {
        int s = 0, e = RP.size() - 1;
        while (s < e) {
            int md = (s + e) / 2;
            vector<int> q(m);
            for (int i = 0; i < n; ++i) ch[i] = 0;
            for (int i = 0; i <= md; ++i) ch[RP[i]] = 1;
            for (int i = 0; i < m; ++i) q[i] = ch[U[i]] ^ ch[V[i]];
            if (ask(q) != d) e = md;
            else s = md + 1;
        }
        R = RP[s];
    }
    answer(L, R);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2424 KB Output is correct
2 Correct 22 ms 3140 KB Output is correct
3 Correct 196 ms 8696 KB Output is correct
4 Correct 228 ms 8704 KB Output is correct
5 Correct 206 ms 8680 KB Output is correct
6 Correct 201 ms 8692 KB Output is correct
7 Correct 215 ms 8708 KB Output is correct
8 Correct 205 ms 8684 KB Output is correct
9 Correct 206 ms 8692 KB Output is correct
10 Correct 215 ms 8700 KB Output is correct
11 Correct 232 ms 8776 KB Output is correct
12 Correct 236 ms 8608 KB Output is correct
13 Correct 220 ms 8580 KB Output is correct
14 Correct 231 ms 8524 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3220 KB Output is correct
2 Correct 43 ms 3712 KB Output is correct
3 Correct 50 ms 4544 KB Output is correct
4 Correct 140 ms 8684 KB Output is correct
5 Correct 155 ms 8664 KB Output is correct
6 Correct 171 ms 8604 KB Output is correct
7 Correct 172 ms 8532 KB Output is correct
8 Correct 156 ms 8592 KB Output is correct
9 Correct 148 ms 8560 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2472 KB Output is correct
2 Correct 24 ms 3188 KB Output is correct
3 Correct 161 ms 7224 KB Output is correct
4 Correct 196 ms 8712 KB Output is correct
5 Correct 214 ms 8688 KB Output is correct
6 Correct 194 ms 8688 KB Output is correct
7 Correct 221 ms 8692 KB Output is correct
8 Correct 231 ms 8680 KB Output is correct
9 Correct 239 ms 8684 KB Output is correct
10 Correct 218 ms 8700 KB Output is correct
11 Correct 192 ms 8560 KB Output is correct
12 Correct 240 ms 8428 KB Output is correct
13 Correct 217 ms 8604 KB Output is correct
14 Correct 229 ms 8740 KB Output is correct
15 Correct 219 ms 8692 KB Output is correct
16 Correct 192 ms 8684 KB Output is correct
17 Correct 233 ms 8564 KB Output is correct
18 Correct 271 ms 8572 KB Output is correct
19 Correct 222 ms 8796 KB Output is correct
20 Correct 230 ms 8560 KB Output is correct
21 Correct 169 ms 8972 KB Output is correct
22 Correct 185 ms 8944 KB Output is correct
23 Correct 219 ms 9132 KB Output is correct
24 Correct 209 ms 9124 KB Output is correct
25 Correct 246 ms 8608 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 3152 KB Output is correct
2 Correct 26 ms 3044 KB Output is correct
3 Correct 257 ms 8852 KB Output is correct
4 Correct 262 ms 9140 KB Output is correct
5 Correct 279 ms 9640 KB Output is correct
6 Correct 294 ms 9660 KB Output is correct
7 Correct 278 ms 9620 KB Output is correct
8 Correct 309 ms 9724 KB Output is correct
9 Correct 260 ms 7252 KB Output is correct
10 Correct 228 ms 7592 KB Output is correct
11 Correct 223 ms 7944 KB Output is correct
12 Correct 318 ms 8952 KB Output is correct
13 Correct 303 ms 9340 KB Output is correct
14 Correct 288 ms 9548 KB Output is correct
15 Correct 318 ms 9592 KB Output is correct
16 Correct 277 ms 7976 KB Output is correct
17 Correct 194 ms 9092 KB Output is correct
18 Correct 193 ms 9052 KB Output is correct
19 Correct 151 ms 9032 KB Output is correct
20 Correct 206 ms 9120 KB Output is correct
21 Correct 311 ms 9512 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3024 KB Output is correct
2 Correct 23 ms 3156 KB Output is correct
3 Correct 213 ms 8976 KB Output is correct
4 Correct 265 ms 8988 KB Output is correct
5 Correct 252 ms 9160 KB Output is correct
6 Correct 328 ms 9624 KB Output is correct
7 Correct 242 ms 8908 KB Output is correct
8 Correct 266 ms 9056 KB Output is correct
9 Correct 269 ms 9208 KB Output is correct
10 Correct 293 ms 9804 KB Output is correct
11 Correct 309 ms 9868 KB Output is correct
12 Correct 297 ms 9732 KB Output is correct
13 Correct 242 ms 7936 KB Output is correct
14 Correct 236 ms 7644 KB Output is correct
15 Correct 233 ms 8008 KB Output is correct
16 Correct 261 ms 7568 KB Output is correct
17 Correct 237 ms 7988 KB Output is correct
18 Correct 269 ms 7552 KB Output is correct
19 Correct 290 ms 8976 KB Output is correct
20 Correct 278 ms 9316 KB Output is correct
21 Correct 289 ms 9552 KB Output is correct
22 Correct 324 ms 9528 KB Output is correct
23 Correct 308 ms 9648 KB Output is correct
24 Correct 311 ms 9600 KB Output is correct
25 Correct 320 ms 9548 KB Output is correct
26 Correct 309 ms 9572 KB Output is correct
27 Correct 210 ms 9144 KB Output is correct
28 Correct 214 ms 9036 KB Output is correct
29 Correct 207 ms 9196 KB Output is correct
30 Correct 186 ms 9068 KB Output is correct
31 Correct 213 ms 9052 KB Output is correct
32 Correct 199 ms 9000 KB Output is correct
33 Correct 203 ms 9148 KB Output is correct
34 Correct 199 ms 9036 KB Output is correct
35 Correct 198 ms 8996 KB Output is correct
36 Correct 188 ms 9016 KB Output is correct
37 Correct 202 ms 9248 KB Output is correct
38 Correct 201 ms 9108 KB Output is correct
39 Correct 319 ms 9612 KB Output is correct
40 Correct 277 ms 9504 KB Output is correct
41 Correct 296 ms 9440 KB Output is correct
42 Correct 300 ms 9664 KB Output is correct