oj.uz

Submission #982850

# Submission time Handle Problem Language Result Execution time Memory
982850 2024-05-14T19:57:51 Z mariaclara Highway Tolls (IOI18_highway) C++17
51 / 100
 149 ms 10964 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});

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

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

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

    vector<int> query(M);
    ll 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,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 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 448 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 448 KB Output is correct
11 Correct 0 ms 700 KB Output is correct
12 Correct 0 ms 440 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 8 ms 1356 KB Output is correct
3 Correct 108 ms 9232 KB Output is correct
4 Correct 99 ms 8728 KB Output is correct
5 Correct 91 ms 8952 KB Output is correct
6 Correct 125 ms 9004 KB Output is correct
7 Correct 101 ms 8800 KB Output is correct
8 Correct 91 ms 9020 KB Output is correct
9 Correct 108 ms 8764 KB Output is correct
10 Correct 92 ms 8828 KB Output is correct
11 Correct 123 ms 8192 KB Output is correct
12 Correct 135 ms 8180 KB Output is correct
13 Correct 101 ms 8440 KB Output is correct
14 Correct 85 ms 7948 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1368 KB Output is correct
2 Correct 21 ms 2140 KB Output is correct
3 Correct 31 ms 3112 KB Output is correct
4 Correct 88 ms 8160 KB Output is correct
5 Correct 93 ms 7952 KB Output is correct
6 Correct 92 ms 7952 KB Output is correct
7 Correct 86 ms 8132 KB Output is correct
8 Correct 96 ms 8200 KB Output is correct
9 Correct 67 ms 7972 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 10 ms 1356 KB Output is correct
3 Correct 67 ms 6784 KB Output is correct
4 Correct 91 ms 8776 KB Output is correct
5 Correct 96 ms 8688 KB Output is correct
6 Correct 85 ms 8744 KB Output is correct
7 Correct 101 ms 8780 KB Output is correct
8 Correct 80 ms 8748 KB Output is correct
9 Correct 90 ms 8744 KB Output is correct
10 Correct 98 ms 9240 KB Output is correct
11 Correct 84 ms 8180 KB Output is correct
12 Correct 77 ms 7956 KB Output is correct
13 Correct 103 ms 8188 KB Output is correct
14 Correct 118 ms 8196 KB Output is correct
15 Correct 107 ms 8784 KB Output is correct
16 Correct 100 ms 8552 KB Output is correct
17 Correct 112 ms 7972 KB Output is correct
18 Correct 83 ms 8188 KB Output is correct
19 Correct 116 ms 8796 KB Output is correct
20 Correct 79 ms 8136 KB Output is correct
21 Correct 80 ms 9328 KB Output is correct
22 Correct 77 ms 9072 KB Output is correct
23 Correct 107 ms 8952 KB Output is correct
24 Correct 113 ms 8636 KB Output is correct
25 Correct 101 ms 8056 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1368 KB Output is correct
2 Correct 18 ms 1424 KB Output is correct
3 Correct 102 ms 9376 KB Output is correct
4 Correct 111 ms 9512 KB Output is correct
5 Incorrect 149 ms 10964 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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