oj.uz

Submission #804755

# Submission time Handle Problem Language Result Execution time Memory
804755 2023-08-03T11:09:46 Z 1bin Highway Tolls (IOI18_highway) C++14
51 / 100
 132 ms 12792 KB 
#include <bits/stdc++.h>
#include "highway.h"

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
ll n, m, lv[NMAX], cost;
vector<pair<int, int>> adj[NMAX];
vector<int> od;


void dfs(int x){
    for(auto&[nx, e] : adj[x])
        if(!lv[nx]){
            lv[nx] = lv[x] + 1;
            dfs(nx);
        }
    od.emplace_back(x);
    return;
}

int find(int rt){
    od.clear();
    memset(lv, 0, sizeof(lv));
    lv[rt] = 1; dfs(rt);
    int l = 0, r = n - 1, mid;
    while(l < r){
        mid = (l + r) / 2;
        vector<int> w(m, 0);
        for(int i = l; i <= mid; i++) 
            for(auto&[j, e] : adj[od[i]])
                if(lv[j] < lv[od[i]]) w[e] = 1;
        if(ask(w) > cost) r = mid;
        else l = mid + 1;
    }
    return od[l];
}

void find_pair(int n_, vector<int> U, std::vector<int> V, int A, int B) {
    n = n_; m = U.size();
    for(int i = 0; i < m; i++){
        adj[U[i]].emplace_back(V[i], i);
        adj[V[i]].emplace_back(U[i], i);
    }
    cost = ask(vector<int>(m, 0));
    int s = find(0);
    int t = find(s);
	answer(s, t);
    return;
}

Compilation message

highway.cpp: In function 'void dfs(int)':
highway.cpp:15:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   15 |     for(auto&[nx, e] : adj[x])
      |              ^
highway.cpp: In function 'int find(int)':
highway.cpp:33:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |             for(auto&[j, e] : adj[od[i]])
      |                      ^

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3408 KB Output is correct
2 Correct 11 ms 4000 KB Output is correct
3 Correct 106 ms 9196 KB Output is correct
4 Correct 115 ms 9068 KB Output is correct
5 Correct 74 ms 9076 KB Output is correct
6 Correct 83 ms 9096 KB Output is correct
7 Correct 106 ms 9072 KB Output is correct
8 Correct 84 ms 9080 KB Output is correct
9 Correct 87 ms 9084 KB Output is correct
10 Correct 80 ms 9080 KB Output is correct
11 Correct 100 ms 9544 KB Output is correct
12 Correct 100 ms 10132 KB Output is correct
13 Correct 109 ms 9652 KB Output is correct
14 Correct 127 ms 9700 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4432 KB Output is correct
2 Correct 22 ms 5492 KB Output is correct
3 Correct 33 ms 6584 KB Output is correct
4 Correct 54 ms 12740 KB Output is correct
5 Correct 72 ms 12740 KB Output is correct
6 Correct 61 ms 12732 KB Output is correct
7 Correct 72 ms 12792 KB Output is correct
8 Correct 77 ms 12748 KB Output is correct
9 Correct 66 ms 12744 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3408 KB Output is correct
2 Correct 9 ms 3996 KB Output is correct
3 Correct 61 ms 7908 KB Output is correct
4 Correct 92 ms 9068 KB Output is correct
5 Correct 87 ms 9072 KB Output is correct
6 Correct 76 ms 9064 KB Output is correct
7 Correct 75 ms 9080 KB Output is correct
8 Correct 79 ms 9072 KB Output is correct
9 Correct 84 ms 9068 KB Output is correct
10 Correct 131 ms 9076 KB Output is correct
11 Correct 125 ms 9440 KB Output is correct
12 Correct 132 ms 10124 KB Output is correct
13 Correct 115 ms 9820 KB Output is correct
14 Correct 94 ms 10020 KB Output is correct
15 Correct 93 ms 9072 KB Output is correct
16 Correct 92 ms 9080 KB Output is correct
17 Correct 123 ms 9808 KB Output is correct
18 Correct 107 ms 9912 KB Output is correct
19 Correct 93 ms 9092 KB Output is correct
20 Correct 103 ms 10372 KB Output is correct
21 Correct 60 ms 9688 KB Output is correct
22 Correct 111 ms 9684 KB Output is correct
23 Correct 83 ms 9276 KB Output is correct
24 Correct 68 ms 9636 KB Output is correct
25 Correct 87 ms 12472 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 4240 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 4244 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -