oj.uz

Submission #982852

# Submission time Handle Problem Language Result Execution time Memory
982852 2024-05-14T20:09:18 Z mariaclara Highway Tolls (IOI18_highway) C++17
90 / 100
 193 ms 11436 KB 
#include "highway.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 4e5+5; 
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    vector<vector<pii>> edges(N);
    int M = sz(U);

    for(int i = 0; i < M; i++)
        edges[U[i]].pb({V[i], i}), edges[V[i]].pb({U[i], i});

    int Raiz = 0;
    vector<int> query(M);
    ll def = ask(query);
    if(M != N-1) {
        int l = 0, r = N-1;

        while(l < r) {
            int mid = (l+r)/2;

            for(int i = 0; i <= mid; i++)
                for(auto [viz,ind] : edges[i])
                    query[ind] = 1;

            if(ask(query) > def) r = mid;
            else l = mid+1;

            for(int i = 0; i < M; i++) query[i] = 0;
        }

        Raiz = l;
    }

    vector<int> dist(N), ord_edges;
    queue<int> fila;
    fila.push(Raiz);

    while(!fila.empty()) {
        int x = fila.front();
        fila.pop();

        for(auto [viz, ind] : edges[x]) {
            if(dist[viz] == 0 and viz != Raiz) {
                dist[viz] = dist[x] + 1;
                ord_edges.pb(ind);
                fila.push(viz);
            }
        }
    }

    query.clear();
    query.resize(M,1);
    for(int i = 0; i < N-1; i++) query[ord_edges[i]] = 0;

    if(def == 0) def = ask(query);

    int l = 0, r = N-1;
    while(l < r) {
        int mid = (l+r)/2;
        for(int i = 0; i <= mid; i++) query[ord_edges[i]] = 0;
        for(int i = mid+1; i < N-1; i++) query[ord_edges[i]] = 1;
        if(ask(query) > def) l = mid+1;
        else r = mid;
    }

    int k = ord_edges[l], S;
    if(dist[U[k]] > dist[V[k]]) S = U[k];
    else S = V[k];

    ord_edges.clear();
    fila.push(S);
    dist.clear();
    dist.resize(N,0);

    while(!fila.empty()) {
        int x = fila.front();
        fila.pop();

        for(auto [viz, ind] : edges[x]) {
            if(dist[viz] == 0 and viz != S) {
                dist[viz] = dist[x] + 1;
                ord_edges.pb(ind);
                fila.push(viz);
            }
        }
    }

    query.clear();
    query.resize(M,1);
    for(int i = 0; i < N-1; i++) query[ord_edges[i]] = 0;

    l = 0;
    r = N-1;
    while(l < r) {
        int mid = (l+r)/2;
        for(int i = 0; i <= mid; i++) query[ord_edges[i]] = 0;
        for(int i = mid+1; i < N-1; i++) query[ord_edges[i]] = 1;
        if(ask(query) > def) l = mid+1;
        else r = mid;
    }

    k = ord_edges[l];
    int T = V[k];
    if(dist[U[k]] > dist[V[k]]) T = U[k];
    
    answer(S,T);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 444 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 1 ms 444 KB Output is correct
4 Correct 0 ms 444 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 440 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 444 KB Output is correct
9 Correct 0 ms 444 KB Output is correct
10 Correct 1 ms 444 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 440 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 520 KB Output is correct
2 Correct 9 ms 1436 KB Output is correct
3 Correct 96 ms 8772 KB Output is correct
4 Correct 89 ms 8780 KB Output is correct
5 Correct 126 ms 9028 KB Output is correct
6 Correct 80 ms 8820 KB Output is correct
7 Correct 81 ms 8780 KB Output is correct
8 Correct 91 ms 9068 KB Output is correct
9 Correct 115 ms 8608 KB Output is correct
10 Correct 87 ms 9004 KB Output is correct
11 Correct 114 ms 8184 KB Output is correct
12 Correct 141 ms 8360 KB Output is correct
13 Correct 98 ms 8572 KB Output is correct
14 Correct 118 ms 8264 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1340 KB Output is correct
2 Correct 12 ms 2568 KB Output is correct
3 Correct 30 ms 3232 KB Output is correct
4 Correct 75 ms 8016 KB Output is correct
5 Correct 99 ms 8200 KB Output is correct
6 Correct 110 ms 8196 KB Output is correct
7 Correct 76 ms 8656 KB Output is correct
8 Correct 104 ms 8204 KB Output is correct
9 Correct 108 ms 8028 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 520 KB Output is correct
2 Correct 11 ms 1348 KB Output is correct
3 Correct 96 ms 7016 KB Output is correct
4 Correct 113 ms 8776 KB Output is correct
5 Correct 130 ms 8800 KB Output is correct
6 Correct 97 ms 8804 KB Output is correct
7 Correct 88 ms 8616 KB Output is correct
8 Correct 88 ms 8776 KB Output is correct
9 Correct 88 ms 9228 KB Output is correct
10 Correct 84 ms 9024 KB Output is correct
11 Correct 118 ms 8220 KB Output is correct
12 Correct 140 ms 8244 KB Output is correct
13 Correct 90 ms 8644 KB Output is correct
14 Correct 141 ms 8432 KB Output is correct
15 Correct 89 ms 8800 KB Output is correct
16 Correct 87 ms 8632 KB Output is correct
17 Correct 146 ms 8180 KB Output is correct
18 Correct 107 ms 8188 KB Output is correct
19 Correct 89 ms 8608 KB Output is correct
20 Correct 108 ms 8196 KB Output is correct
21 Correct 82 ms 9072 KB Output is correct
22 Correct 92 ms 9076 KB Output is correct
23 Correct 89 ms 9296 KB Output is correct
24 Correct 104 ms 8992 KB Output is correct
25 Correct 115 ms 8104 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1380 KB Output is correct
2 Correct 13 ms 1468 KB Output is correct
3 Correct 118 ms 9388 KB Output is correct
4 Correct 162 ms 9528 KB Output is correct
5 Correct 159 ms 10780 KB Output is correct
6 Correct 166 ms 11436 KB Output is correct
7 Correct 150 ms 10960 KB Output is correct
8 Correct 169 ms 10524 KB Output is correct
9 Correct 116 ms 7416 KB Output is correct
10 Correct 98 ms 7744 KB Output is correct
11 Correct 130 ms 8204 KB Output is correct
12 Correct 187 ms 9628 KB Output is correct
13 Correct 188 ms 10132 KB Output is correct
14 Correct 176 ms 11016 KB Output is correct
15 Correct 179 ms 10964 KB Output is correct
16 Correct 147 ms 8708 KB Output is correct
17 Correct 106 ms 9424 KB Output is correct
18 Correct 99 ms 9380 KB Output is correct
19 Correct 111 ms 9480 KB Output is correct
20 Correct 106 ms 9856 KB Output is correct
21 Correct 160 ms 10760 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1284 KB Output is correct
2 Correct 19 ms 1452 KB Output is correct
3 Partially correct 135 ms 9308 KB Output is partially correct
4 Partially correct 151 ms 9380 KB Output is partially correct
5 Correct 159 ms 9752 KB Output is correct
6 Partially correct 163 ms 10744 KB Output is partially correct
7 Partially correct 119 ms 9680 KB Output is partially correct
8 Correct 130 ms 9292 KB Output is correct
9 Partially correct 127 ms 9740 KB Output is partially correct
10 Correct 182 ms 10732 KB Output is correct
11 Partially correct 165 ms 10748 KB Output is partially correct
12 Partially correct 135 ms 10748 KB Output is partially correct
13 Correct 126 ms 8428 KB Output is correct
14 Correct 136 ms 7696 KB Output is correct
15 Correct 118 ms 7984 KB Output is correct
16 Correct 111 ms 7524 KB Output is correct
17 Correct 125 ms 8868 KB Output is correct
18 Correct 137 ms 7580 KB Output is correct
19 Correct 152 ms 9632 KB Output is correct
20 Correct 193 ms 10080 KB Output is correct
21 Correct 185 ms 11012 KB Output is correct
22 Correct 140 ms 10756 KB Output is correct
23 Partially correct 157 ms 10728 KB Output is partially correct
24 Partially correct 185 ms 10764 KB Output is partially correct
25 Partially correct 177 ms 11208 KB Output is partially correct
26 Correct 173 ms 10772 KB Output is correct
27 Partially correct 91 ms 9096 KB Output is partially correct
28 Partially correct 140 ms 9080 KB Output is partially correct
29 Correct 93 ms 9452 KB Output is correct
30 Correct 93 ms 9336 KB Output is correct
31 Partially correct 116 ms 9288 KB Output is partially correct
32 Partially correct 106 ms 9444 KB Output is partially correct
33 Correct 92 ms 9472 KB Output is correct
34 Correct 104 ms 9508 KB Output is correct
35 Partially correct 104 ms 9524 KB Output is partially correct
36 Correct 99 ms 9176 KB Output is correct
37 Correct 112 ms 9456 KB Output is correct
38 Partially correct 129 ms 9328 KB Output is partially correct
39 Correct 178 ms 10740 KB Output is correct
40 Correct 158 ms 10980 KB Output is correct
41 Correct 134 ms 10748 KB Output is correct
42 Partially correct 119 ms 10536 KB Output is partially correct