oj.uz

Submission #818374

# Submission time Handle Problem Language Result Execution time Memory
818374 2023-08-10T04:32:58 Z Jarif_Rahman Highway Tolls (IOI18_highway) C++17
90 / 100
 176 ms 11056 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
 
int n, m;
ll A, B;
vector<vector<pair<int, int>>> graph;
 
ll def;
 
int find_node(int root){
    vector<int> dis(n, -1);
    queue<int> Q;
    dis[root] = 0;
    Q.push(root);
    vector<int> p(n, -1), W(m, 1);
    while(!Q.empty()){
        int nd = Q.front(); Q.pop();
        for(auto [x, i]: graph[nd]) if(dis[x] == -1){
            dis[x] = dis[nd]+1;
            p[x] = i;
            W[i] = 0;
            Q.push(x);
        }
    }
 
    vector<int> o(n);
    for(int i = 0; i < n; i++) o[i] = i;
    sort(o.begin(), o.end(), [&](int a, int b){
        return dis[a] > dis[b];
    });
  
    int a = 0, b = n-1;
    while(a < b){
        int md = (a+b)/2;
        vector<int> w = W;
        for(int i = 0; i <= md; i++) if(p[o[i]] != -1) w[p[o[i]]] = 1;
        ll x = ask(w);
        if(x > def) b = md;
        else a = md+1;
    }
 
    return o[a];
}
 
void find_pair(int _n, vector<int> U, vector<int> V, int _A, int _B){
    swap(n, _n);
    m = U.size();
    A = _A, B = _B;
    graph.resize(n);
 
    for(int i = 0; i < m; i++){
        graph[U[i]].pb({V[i], i});
        graph[V[i]].pb({U[i], i});
    }
 
    def = ask(vector<int>(m, 0));
 
    int a = 0, b = m-1;
    while(a < b){
        int md = (a+b)/2;
        vector<int> w(m, 0);
        for(int i = 0; i <= md; i++) w[i] = 1;
        ll x = ask(w);
        if(x > def) b = md;
        else a = md+1;
    }
 
    int nd = U[a];
    int s = find_node(nd);
    int t = find_node(s);
    answer(s, t);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 9 ms 1232 KB Output is correct
3 Correct 90 ms 9004 KB Output is correct
4 Correct 110 ms 9032 KB Output is correct
5 Correct 117 ms 9100 KB Output is correct
6 Correct 103 ms 9080 KB Output is correct
7 Correct 103 ms 9024 KB Output is correct
8 Correct 103 ms 9040 KB Output is correct
9 Correct 102 ms 9004 KB Output is correct
10 Correct 116 ms 9116 KB Output is correct
11 Correct 127 ms 8420 KB Output is correct
12 Correct 103 ms 8424 KB Output is correct
13 Correct 110 ms 8412 KB Output is correct
14 Correct 121 ms 8436 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1104 KB Output is correct
2 Correct 27 ms 2072 KB Output is correct
3 Correct 23 ms 2988 KB Output is correct
4 Correct 96 ms 8412 KB Output is correct
5 Correct 96 ms 8412 KB Output is correct
6 Correct 97 ms 8400 KB Output is correct
7 Correct 75 ms 8416 KB Output is correct
8 Correct 87 ms 8404 KB Output is correct
9 Correct 63 ms 8408 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 12 ms 1264 KB Output is correct
3 Correct 89 ms 7080 KB Output is correct
4 Correct 82 ms 9000 KB Output is correct
5 Correct 84 ms 8992 KB Output is correct
6 Correct 85 ms 9064 KB Output is correct
7 Correct 110 ms 9016 KB Output is correct
8 Correct 73 ms 8984 KB Output is correct
9 Correct 91 ms 9004 KB Output is correct
10 Correct 110 ms 9012 KB Output is correct
11 Correct 122 ms 8408 KB Output is correct
12 Correct 117 ms 8404 KB Output is correct
13 Correct 108 ms 8416 KB Output is correct
14 Correct 114 ms 8424 KB Output is correct
15 Correct 85 ms 9012 KB Output is correct
16 Correct 99 ms 9008 KB Output is correct
17 Correct 102 ms 8400 KB Output is correct
18 Correct 157 ms 8408 KB Output is correct
19 Correct 111 ms 9012 KB Output is correct
20 Correct 110 ms 8412 KB Output is correct
21 Correct 87 ms 9484 KB Output is correct
22 Correct 122 ms 9500 KB Output is correct
23 Correct 79 ms 9332 KB Output is correct
24 Correct 76 ms 9468 KB Output is correct
25 Correct 99 ms 8532 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1284 KB Output is correct
2 Correct 11 ms 1224 KB Output is correct
3 Correct 137 ms 9416 KB Output is correct
4 Correct 137 ms 9920 KB Output is correct
5 Correct 137 ms 10948 KB Output is correct
6 Correct 139 ms 11052 KB Output is correct
7 Correct 133 ms 10956 KB Output is correct
8 Correct 142 ms 10960 KB Output is correct
9 Correct 107 ms 7496 KB Output is correct
10 Correct 93 ms 7780 KB Output is correct
11 Correct 99 ms 8452 KB Output is correct
12 Correct 119 ms 10056 KB Output is correct
13 Correct 125 ms 10516 KB Output is correct
14 Correct 142 ms 10956 KB Output is correct
15 Correct 142 ms 11056 KB Output is correct
16 Correct 110 ms 8624 KB Output is correct
17 Correct 88 ms 9540 KB Output is correct
18 Correct 81 ms 9880 KB Output is correct
19 Correct 77 ms 9748 KB Output is correct
20 Correct 80 ms 9736 KB Output is correct
21 Correct 137 ms 10940 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1224 KB Output is correct
2 Correct 13 ms 1360 KB Output is correct
3 Partially correct 90 ms 9464 KB Output is partially correct
4 Partially correct 116 ms 9708 KB Output is partially correct
5 Correct 123 ms 9924 KB Output is correct
6 Partially correct 136 ms 10956 KB Output is partially correct
7 Partially correct 105 ms 9444 KB Output is partially correct
8 Partially correct 102 ms 9656 KB Output is partially correct
9 Correct 114 ms 9924 KB Output is correct
10 Partially correct 130 ms 11040 KB Output is partially correct
11 Partially correct 146 ms 10948 KB Output is partially correct
12 Partially correct 124 ms 11012 KB Output is partially correct
13 Correct 110 ms 8452 KB Output is correct
14 Correct 107 ms 7788 KB Output is correct
15 Correct 106 ms 8452 KB Output is correct
16 Correct 101 ms 7776 KB Output is correct
17 Correct 102 ms 8444 KB Output is correct
18 Correct 96 ms 7832 KB Output is correct
19 Correct 133 ms 10040 KB Output is correct
20 Correct 128 ms 10520 KB Output is correct
21 Partially correct 137 ms 10996 KB Output is partially correct
22 Correct 135 ms 10936 KB Output is correct
23 Correct 140 ms 10940 KB Output is correct
24 Partially correct 153 ms 10960 KB Output is partially correct
25 Partially correct 138 ms 11036 KB Output is partially correct
26 Partially correct 134 ms 10976 KB Output is partially correct
27 Partially correct 83 ms 9684 KB Output is partially correct
28 Partially correct 89 ms 9580 KB Output is partially correct
29 Partially correct 87 ms 9896 KB Output is partially correct
30 Correct 91 ms 9696 KB Output is correct
31 Correct 86 ms 9756 KB Output is correct
32 Partially correct 85 ms 9688 KB Output is partially correct
33 Correct 90 ms 9808 KB Output is correct
34 Partially correct 77 ms 9640 KB Output is partially correct
35 Correct 84 ms 9632 KB Output is correct
36 Partially correct 115 ms 9532 KB Output is partially correct
37 Partially correct 86 ms 9752 KB Output is partially correct
38 Partially correct 92 ms 9696 KB Output is partially correct
39 Partially correct 176 ms 10952 KB Output is partially correct
40 Partially correct 140 ms 10944 KB Output is partially correct
41 Partially correct 137 ms 10916 KB Output is partially correct
42 Partially correct 140 ms 10932 KB Output is partially correct