oj.uz

Submission #405016

# Submission time Handle Problem Language Result Execution time Memory
405016 2021-05-15T14:52:28 Z phathnv Highway Tolls (IOI18_highway) C++11
90 / 100
 362 ms 14836 KB 
#include <bits/stdc++.h>
#include "highway.h"

using namespace std;

const int MAXN = 90000;

int n, m, tIn[MAXN], timer;
vector<int> u, v, adj[MAXN], adjTree[MAXN];
bool visited[MAXN];
long long allA;

void Dfs(int u, int p) {
    tIn[u] = timer++;
    for(int v : adjTree[u])
        if (v != p)
            Dfs(v, u);
}

void BuildTree(int s) {
    timer = 0;
    for(int i = 0; i < n; i++){
        adjTree[i].clear();
        visited[i] = 0;
    }
    queue<int> qu;
    visited[s] = 1;
    tIn[s] = timer++;
    qu.push(s);
    while (!qu.empty()) {
        int u = qu.front();
        qu.pop();
        for(int v : adj[u])
            if (!visited[v]) {
                visited[v] = 1;
                tIn[v] = timer++;
                qu.push(v);
                adjTree[u].push_back(v);
                adjTree[v].push_back(u);
            }
    }
    //timer = 0;
    //Dfs(s, -1);
}

long long MyAsk(int l, int r) {
    vector<int> w(m);
    for(int i = 0; i < m; i++)
        if ((l <= tIn[u[i]] && tIn[u[i]] <= r) || (l <= tIn[v[i]] && tIn[v[i]] <= r))
            w[i] = 1;
        else
            w[i] = 0;
    return ask(w);
}

int Find_city() {
    assert(timer == n);
    int l = 0, r = n - 1, res = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (MyAsk(mid, n - 1) != allA) {
            res = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    for(int i = 0; i < n; i++)
        if (tIn[i] == res)
            return i;
    assert(0);
}

void find_pair(int _n, vector<int> _u, vector<int> _v, int a, int b) {
    n = _n;
    u = _u;
    v = _v;
    m = u.size();
    for(int i = 0; i < m; i++) {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    iota(tIn, tIn + n, 0);
    timer = n;
    allA = MyAsk(-1, -1);
    int root = Find_city();
    BuildTree(root);
    int s = Find_city();
    BuildTree(s);
    int t = Find_city();
    answer(s, t);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4552 KB Output is correct
2 Correct 17 ms 5424 KB Output is correct
3 Correct 215 ms 13308 KB Output is correct
4 Correct 227 ms 13316 KB Output is correct
5 Correct 214 ms 13300 KB Output is correct
6 Correct 189 ms 13404 KB Output is correct
7 Correct 256 ms 13340 KB Output is correct
8 Correct 215 ms 13300 KB Output is correct
9 Correct 245 ms 13316 KB Output is correct
10 Correct 219 ms 13352 KB Output is correct
11 Correct 227 ms 13176 KB Output is correct
12 Correct 265 ms 13084 KB Output is correct
13 Correct 205 ms 13072 KB Output is correct
14 Correct 270 ms 13064 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5416 KB Output is correct
2 Correct 36 ms 6404 KB Output is correct
3 Correct 41 ms 7360 KB Output is correct
4 Correct 125 ms 13064 KB Output is correct
5 Correct 138 ms 13136 KB Output is correct
6 Correct 145 ms 13064 KB Output is correct
7 Correct 135 ms 13072 KB Output is correct
8 Correct 109 ms 13064 KB Output is correct
9 Correct 166 ms 13080 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4596 KB Output is correct
2 Correct 26 ms 5496 KB Output is correct
3 Correct 120 ms 11388 KB Output is correct
4 Correct 233 ms 13304 KB Output is correct
5 Correct 196 ms 13312 KB Output is correct
6 Correct 181 ms 13316 KB Output is correct
7 Correct 208 ms 13312 KB Output is correct
8 Correct 246 ms 13296 KB Output is correct
9 Correct 253 ms 13312 KB Output is correct
10 Correct 247 ms 13436 KB Output is correct
11 Correct 263 ms 13064 KB Output is correct
12 Correct 209 ms 13060 KB Output is correct
13 Correct 259 ms 13236 KB Output is correct
14 Correct 248 ms 13184 KB Output is correct
15 Correct 219 ms 13400 KB Output is correct
16 Correct 174 ms 13320 KB Output is correct
17 Correct 215 ms 13100 KB Output is correct
18 Correct 248 ms 13068 KB Output is correct
19 Correct 198 ms 13308 KB Output is correct
20 Correct 223 ms 13244 KB Output is correct
21 Correct 215 ms 14160 KB Output is correct
22 Correct 177 ms 14244 KB Output is correct
23 Correct 176 ms 13956 KB Output is correct
24 Correct 201 ms 13884 KB Output is correct
25 Correct 191 ms 13192 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5500 KB Output is correct
2 Correct 31 ms 5512 KB Output is correct
3 Correct 233 ms 13676 KB Output is correct
4 Correct 303 ms 14112 KB Output is correct
5 Correct 359 ms 14732 KB Output is correct
6 Correct 353 ms 14708 KB Output is correct
7 Correct 360 ms 14796 KB Output is correct
8 Correct 316 ms 14720 KB Output is correct
9 Correct 269 ms 11332 KB Output is correct
10 Correct 256 ms 11404 KB Output is correct
11 Correct 226 ms 12424 KB Output is correct
12 Correct 257 ms 13588 KB Output is correct
13 Correct 348 ms 14132 KB Output is correct
14 Correct 314 ms 14488 KB Output is correct
15 Correct 309 ms 14432 KB Output is correct
16 Correct 225 ms 12128 KB Output is correct
17 Correct 176 ms 14368 KB Output is correct
18 Correct 194 ms 14440 KB Output is correct
19 Correct 182 ms 14368 KB Output is correct
20 Correct 205 ms 14444 KB Output is correct
21 Correct 279 ms 14556 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5456 KB Output is correct
2 Correct 22 ms 5480 KB Output is correct
3 Partially correct 253 ms 13716 KB Output is partially correct
4 Correct 233 ms 13928 KB Output is correct
5 Partially correct 238 ms 14140 KB Output is partially correct
6 Correct 319 ms 14736 KB Output is correct
7 Correct 276 ms 13780 KB Output is correct
8 Partially correct 240 ms 13912 KB Output is partially correct
9 Correct 227 ms 14036 KB Output is correct
10 Partially correct 356 ms 14836 KB Output is partially correct
11 Partially correct 328 ms 14768 KB Output is partially correct
12 Partially correct 362 ms 14764 KB Output is partially correct
13 Correct 245 ms 12424 KB Output is correct
14 Correct 216 ms 11356 KB Output is correct
15 Correct 277 ms 11928 KB Output is correct
16 Correct 261 ms 11396 KB Output is correct
17 Correct 247 ms 12420 KB Output is correct
18 Correct 275 ms 11420 KB Output is correct
19 Correct 307 ms 13416 KB Output is correct
20 Partially correct 257 ms 13880 KB Output is partially correct
21 Partially correct 305 ms 14448 KB Output is partially correct
22 Correct 300 ms 14500 KB Output is correct
23 Correct 295 ms 14424 KB Output is correct
24 Partially correct 335 ms 14592 KB Output is partially correct
25 Partially correct 278 ms 14488 KB Output is partially correct
26 Partially correct 301 ms 14432 KB Output is partially correct
27 Correct 231 ms 14352 KB Output is correct
28 Partially correct 222 ms 14236 KB Output is partially correct
29 Correct 222 ms 14636 KB Output is correct
30 Correct 223 ms 14328 KB Output is correct
31 Correct 232 ms 14472 KB Output is correct
32 Correct 172 ms 14300 KB Output is correct
33 Correct 222 ms 14656 KB Output is correct
34 Partially correct 241 ms 14316 KB Output is partially correct
35 Correct 195 ms 14312 KB Output is correct
36 Partially correct 208 ms 14284 KB Output is partially correct
37 Partially correct 241 ms 14732 KB Output is partially correct
38 Partially correct 184 ms 14332 KB Output is partially correct
39 Correct 263 ms 14484 KB Output is correct
40 Partially correct 313 ms 14356 KB Output is partially correct
41 Correct 298 ms 14420 KB Output is correct
42 Correct 238 ms 14388 KB Output is correct