oj.uz

Submission #1021447

# Submission time Handle Problem Language Result Execution time Memory
1021447 2024-07-12T18:22:30 Z Zicrus Highway Tolls (IOI18_highway) C++17
5 / 100
 84 ms 10456 KB 
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;

typedef long long ll;

vector<vector<pair<int, int>>> adj;
vector<pair<int, int>> sorted;
vector<bool> vst;
vector<int> nDist;

void dfs(int a, int dist) {
    if (vst[a]) return;
    vst[a] = true;

    nDist[a] = dist - 1;

    for (auto &e : adj[a]) {
        if (vst[e.first]) continue;
        sorted.push_back({dist, e.second});
        dfs(e.first, dist + 1);
    }
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    int M = U.size();
    adj = vector<vector<pair<int, int>>>(N);
    sorted = vector<pair<int, int>>();
    for (int i = 0; i < M; i++) {
        adj[U[i]].push_back({V[i], i});
        adj[V[i]].push_back({U[i], i});
    }

    int S = 0;
    /*vst = vector<bool>(N);
    nDist = vector<int>(N);
    dfs(0, 1);
    sort(sorted.begin(), sorted.end());

    vector<int> tst(M);
    ll ctrl = ask(tst);

    int begin = 0;
    int end = M - 1;
    while (begin < end) {
        vector<int> w(M);
        int mid = (begin + end + 1) / 2;
        for (int i = mid; i <= end; i++) {
            w[sorted[i].second] = 1;
        }
        ll res = ask(w);
        if (res > ctrl) {
            begin = mid;
        }
        else {
            end = mid - 1;
        }
    }

    pair<int, int> sEdge = sorted[begin];
    int S = 0;
    for (int i = 0; i < N; i++) {
        bool hasS = false, further = nDist[i] == sEdge.first;
        for (auto &e : adj[i]) {
            if (e.second == sEdge.second) hasS = true;
        }
        if (hasS && further) {
            S = i;
            break;
        }
    }*/

    //cout << S << '\n';

    vst = vector<bool>(N);
    nDist = vector<int>(N);
    sorted = vector<pair<int, int>>();
    dfs(S, 1);
    sort(sorted.begin(), sorted.end());

    vector<int> tst(M);
    ll ctrl = ask(tst);
    int begin = 0;
    int end = M - 1;
    begin = -1;
    for (int i = 0; i < M; i++) {
        if (sorted[i].first == ctrl && begin == -1) begin = i;
        if (sorted[i].first == ctrl) end = i;
    }
    while (begin < end) {
        vector<int> w(M);
        int mid = (begin + end + 1) / 2;
        for (int i = mid; i <= end; i++) {
            w[sorted[i].second] = 1;
        }
        ll res = ask(w);
        if (res > ctrl) {
            begin = mid;
        }
        else {
            end = mid - 1;
        }
    }

    pair<int, int> tEdge = sorted[begin];
    int T = 0;
    for (int i = 0; i < N; i++) {
        bool hasT = false, further = nDist[i] == tEdge.first;
        for (auto &e : adj[i]) {
            if (e.second == tEdge.second) hasT = true;
        }
        if (hasT && further) {
            T = i;
            break;
        }
    }

    answer(S, T);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 8 ms 1368 KB Output is correct
3 Correct 76 ms 9116 KB Output is correct
4 Correct 84 ms 8916 KB Output is correct
5 Correct 68 ms 8916 KB Output is correct
6 Correct 83 ms 9100 KB Output is correct
7 Correct 69 ms 8932 KB Output is correct
8 Correct 74 ms 8936 KB Output is correct
9 Correct 69 ms 8948 KB Output is correct
10 Correct 77 ms 9004 KB Output is correct
11 Correct 69 ms 9668 KB Output is correct
12 Correct 72 ms 10456 KB Output is correct
13 Incorrect 69 ms 9936 KB Output is incorrect: {s, t} is wrong.
14 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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