oj.uz

Submission #982843

# Submission time Handle Problem Language Result Execution time Memory
982843 2024-05-14T19:48:23 Z mariaclara Highway Tolls (IOI18_highway) C++17
6 / 100
 133 ms 10996 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; 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; 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 444 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 448 KB Output is correct
11 Correct 1 ms 444 KB Output is correct
12 Incorrect 1 ms 440 KB Output is incorrect: {s, t} is wrong.
13 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 14 ms 1460 KB Output is correct
3 Correct 86 ms 9012 KB Output is correct
4 Correct 86 ms 8960 KB Output is correct
5 Correct 128 ms 8508 KB Output is correct
6 Correct 84 ms 8936 KB Output is correct
7 Correct 100 ms 9032 KB Output is correct
8 Correct 100 ms 8784 KB Output is correct
9 Correct 85 ms 8964 KB Output is correct
10 Correct 94 ms 8772 KB Output is correct
11 Correct 94 ms 7956 KB Output is correct
12 Correct 100 ms 8432 KB Output is correct
13 Correct 91 ms 8420 KB Output is correct
14 Incorrect 97 ms 8204 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1368 KB Output is correct
2 Correct 14 ms 2644 KB Output is correct
3 Correct 31 ms 3116 KB Output is correct
4 Correct 82 ms 7948 KB Output is correct
5 Correct 75 ms 7948 KB Output is correct
6 Correct 93 ms 8200 KB Output is correct
7 Correct 85 ms 7968 KB Output is correct
8 Correct 68 ms 7948 KB Output is correct
9 Correct 72 ms 8156 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 9 ms 1708 KB Output is correct
3 Correct 66 ms 7276 KB Output is correct
4 Correct 85 ms 8764 KB Output is correct
5 Correct 103 ms 8732 KB Output is correct
6 Correct 90 ms 8496 KB Output is correct
7 Correct 108 ms 8552 KB Output is correct
8 Correct 109 ms 8748 KB Output is correct
9 Correct 114 ms 9020 KB Output is correct
10 Correct 98 ms 8788 KB Output is correct
11 Correct 121 ms 8188 KB Output is correct
12 Correct 101 ms 8188 KB Output is correct
13 Correct 119 ms 8424 KB Output is correct
14 Correct 91 ms 8436 KB Output is correct
15 Correct 85 ms 8800 KB Output is correct
16 Correct 82 ms 8800 KB Output is correct
17 Correct 105 ms 7952 KB Output is correct
18 Incorrect 74 ms 8416 KB Output is incorrect: {s, t} is wrong.
19 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1368 KB Output is correct
2 Correct 15 ms 1512 KB Output is correct
3 Correct 130 ms 9832 KB Output is correct
4 Correct 101 ms 9972 KB Output is correct
5 Incorrect 133 ms 10996 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 12 ms 1280 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -