oj.uz

Submission #818425

# Submission time Handle Problem Language Result Execution time Memory
818425 2023-08-10T04:49:19 Z Jarif_Rahman Highway Tolls (IOI18_highway) C++17
51 / 100
 189 ms 12536 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;
 
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});
    }
 
    ll 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 u = U[a], v = V[a];

    vector<int> disu(n, -1);
    queue<int> Q;
    disu[u] = 0;
    Q.push(u);
    vector<int> pu(n, -1), wu(m, 1);
    while(!Q.empty()){
        int nd = Q.front(); Q.pop();
        for(auto [x, i]: graph[nd]) if(disu[x] == -1){
            disu[x] = disu[nd]+1;
            pu[x] = i;
            wu[i] = 0;
            Q.push(x);
        }
    }

    vector<int> disv(n, -1);
    disv[v] = 0;
    Q.push(v);
    vector<int> pv(n, -1), wv(m, 1);
    while(!Q.empty()){
        int nd = Q.front(); Q.pop();
        for(auto [x, i]: graph[nd]) if(disv[x] == -1){
            disv[x] = disv[nd]+1;
            pv[x] = i;
            wv[i] = 0;
            Q.push(x);
        }
    }

    vector<int> unodes, vnodes;
    for(int i = 0; i < n; i++){
        if(disu[i] == disv[i]) continue;
        if(disu[i] < disv[i]) unodes.pb(i);
        else vnodes.pb(i);
    }

    sort(unodes.begin(), unodes.end(), [&](int x, int y){
        return disu[x] > disu[y];
    });
    sort(vnodes.begin(), vnodes.end(), [&](int x, int y){
        return disv[x] > disv[y];
    });

    int s, t;

    a = 0, b = int(unodes.size())-1;
    while(a < b){
        int md = (a+b)/2;
        vector<int> w = wu;
        for(int i = 0; i <= md; i++) if(pu[unodes[i]] != -1) w[pu[unodes[i]]] = 1;
        ll x = ask(w);
        if(x > def) b = md;
        else a = md+1;
    }
    s = unodes[a];

    a = 0, b = int(vnodes.size())-1;
    while(a < b){
        int md = (a+b)/2;
        vector<int> w = wv;
        for(int i = 0; i <= md; i++) if(pv[vnodes[i]] != -1) w[pv[vnodes[i]]] = 1;
        ll x = ask(w);
        if(x > def) b = md;
        else a = md+1;
    }
    t = vnodes[a];

    answer(s, t);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 8 ms 1376 KB Output is correct
3 Correct 79 ms 10228 KB Output is correct
4 Correct 116 ms 10288 KB Output is correct
5 Correct 89 ms 10204 KB Output is correct
6 Correct 80 ms 10208 KB Output is correct
7 Correct 82 ms 10204 KB Output is correct
8 Correct 120 ms 10212 KB Output is correct
9 Correct 82 ms 10204 KB Output is correct
10 Correct 125 ms 10204 KB Output is correct
11 Correct 112 ms 9812 KB Output is correct
12 Correct 132 ms 9644 KB Output is correct
13 Correct 93 ms 9608 KB Output is correct
14 Correct 104 ms 9588 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1232 KB Output is correct
2 Correct 14 ms 2396 KB Output is correct
3 Correct 20 ms 3368 KB Output is correct
4 Correct 89 ms 9724 KB Output is correct
5 Correct 65 ms 9724 KB Output is correct
6 Correct 82 ms 9624 KB Output is correct
7 Correct 95 ms 9608 KB Output is correct
8 Correct 73 ms 9760 KB Output is correct
9 Correct 93 ms 9632 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 11 ms 1396 KB Output is correct
3 Correct 70 ms 8100 KB Output is correct
4 Correct 98 ms 10196 KB Output is correct
5 Correct 76 ms 10208 KB Output is correct
6 Correct 110 ms 10204 KB Output is correct
7 Correct 80 ms 10212 KB Output is correct
8 Correct 74 ms 10196 KB Output is correct
9 Correct 108 ms 10200 KB Output is correct
10 Correct 81 ms 10308 KB Output is correct
11 Correct 107 ms 9620 KB Output is correct
12 Correct 130 ms 9576 KB Output is correct
13 Correct 101 ms 9652 KB Output is correct
14 Correct 105 ms 9712 KB Output is correct
15 Correct 106 ms 10216 KB Output is correct
16 Correct 80 ms 10212 KB Output is correct
17 Correct 88 ms 9604 KB Output is correct
18 Correct 84 ms 9628 KB Output is correct
19 Correct 73 ms 10224 KB Output is correct
20 Correct 100 ms 9668 KB Output is correct
21 Correct 94 ms 10816 KB Output is correct
22 Correct 68 ms 10804 KB Output is correct
23 Correct 77 ms 10704 KB Output is correct
24 Correct 80 ms 10480 KB Output is correct
25 Correct 88 ms 9800 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1524 KB Output is correct
2 Correct 12 ms 1440 KB Output is correct
3 Correct 122 ms 10584 KB Output is correct
4 Correct 124 ms 11200 KB Output is correct
5 Correct 161 ms 12156 KB Output is correct
6 Correct 122 ms 12284 KB Output is correct
7 Correct 150 ms 12248 KB Output is correct
8 Incorrect 189 ms 12276 KB Output is incorrect: {s, t} is wrong.
9 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1360 KB Output is correct
2 Correct 13 ms 1488 KB Output is correct
3 Correct 96 ms 10740 KB Output is correct
4 Correct 119 ms 10852 KB Output is correct
5 Correct 136 ms 11276 KB Output is correct
6 Correct 124 ms 12284 KB Output is correct
7 Correct 127 ms 10632 KB Output is correct
8 Correct 122 ms 10792 KB Output is correct
9 Correct 117 ms 11288 KB Output is correct
10 Correct 119 ms 12372 KB Output is correct
11 Correct 163 ms 12536 KB Output is correct
12 Correct 119 ms 12276 KB Output is correct
13 Incorrect 118 ms 9448 KB Output is incorrect: {s, t} is wrong.
14 Halted 0 ms 0 KB -