oj.uz

Submission #587309

# Submission time Handle Problem Language Result Execution time Memory
587309 2022-07-01T15:51:23 Z Josia Highway Tolls (IOI18_highway) C++14
51 / 100
 234 ms 21676 KB 
#include <bits/stdc++.h>
#include "highway.h"

using namespace std;

#define int long long

vector<vector<int>> graph;
int normal;
map<pair<int, int>, int> edgeToIndex;

int bsEdges(int M) {
    int l=0; int r = M-1;

    while (l<r) {
        vector<signed> a(M, 0);
        int m = (l + r) / 2;
        for (int i=l; i<=m; i++) {
            a[i] = 1;
        }
        if (ask(a) != normal) {
            r = m;
        }
        else {
            l = m+1;
        }
    }

    return l;
}



vector<int> side;
vector<bool> visited;



void sideDFS(int v) {
    if (visited[v]) return;
    visited[v] = 1;

    side[v] = 1;

    for (int i: graph[v]) {
        sideDFS(i);
    }
}



vector<pair<int, int>> cand;

void findLevel(int v, int t, int l, int p) {
    if (visited[v]) return;
    visited[v] = 1;

    if (l == t) {
        cand.push_back({v, p});
    }

    for (int i: graph[v]) {
        findLevel(i, t, l+1, v);
    }
}



int BS2(vector<pair<int, int>> edges, int M) {
    int l = 0; int r = edges.size()-1;


    while (l<r) {
        vector<signed> a(M, 0);
        int m = (l + r) / 2;
        for (int i=l; i<=m; i++) {
            a[edgeToIndex[{min(edges[i].first, edges[i].second), max(edges[i].first, edges[i].second)}]] = 1;
        }
        if (ask(a) != normal) {
            r = m;
        }
        else {
            l = m+1;
        }
    }

    return edges[l].first;
}



void find_pair(signed N, std::vector<signed> U, std::vector<signed> V, signed A, signed B) {
    int M = U.size();
    assert(M == N-1);

    vector<signed> a(M, 0);
    normal = ask(a);

    vector<pair<int, int>> edges;
    graph.clear();
    graph.resize(N);

    edgeToIndex.clear();

    for (int i=0; i<M; i++) {
        edges.push_back({min(U[i], V[i]), max(U[i], V[i])});
        graph[U[i]].push_back(V[i]);
        graph[V[i]].push_back(U[i]);
        edgeToIndex[{min(U[i], V[i]), max(U[i], V[i])}] = i;
    }

    pair<int, int> edgeOnPath = edges[bsEdges(M)];


    side.assign(N, 0);
    visited.assign(N, 0);

    visited[edgeOnPath.second] = 1;
    sideDFS(edgeOnPath.first);

    pair<int, int> length;

    {
        vector<signed> askk(M, 0);
        for (int i=0; i<M; i++) {
            if (side[edges[i].first] && side[edges[i].second]) askk[i] = 1;
        }
        int tmp = ask(askk);


        length.first = ((tmp-normal)/(B-A));
        length.second = ((normal - (length.first * A)) / A) -1;
    }


    visited.assign(N, 0);
    cand.clear();

    visited[edgeOnPath.second] = 1;

    findLevel(edgeOnPath.first, length.first, 0, -1);


    int start = length.first > 0 ? BS2(cand, M) : edgeOnPath.first;



    visited.assign(N, 0);
    cand.clear();

    visited[edgeOnPath.first] = 1;

    findLevel(edgeOnPath.second, length.second, 0, -1);

    int end = length.second > 0 ? BS2(cand, M) : edgeOnPath.second;



    answer(min(start, end), max(start, end));
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 300 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 2 ms 464 KB Output is correct
2 Correct 15 ms 1996 KB Output is correct
3 Correct 185 ms 16180 KB Output is correct
4 Correct 190 ms 16040 KB Output is correct
5 Correct 171 ms 16064 KB Output is correct
6 Correct 169 ms 15792 KB Output is correct
7 Correct 186 ms 16172 KB Output is correct
8 Correct 202 ms 15672 KB Output is correct
9 Correct 201 ms 15692 KB Output is correct
10 Correct 187 ms 16080 KB Output is correct
11 Correct 155 ms 16364 KB Output is correct
12 Correct 172 ms 17344 KB Output is correct
13 Correct 157 ms 16812 KB Output is correct
14 Correct 170 ms 16936 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2528 KB Output is correct
2 Correct 21 ms 4780 KB Output is correct
3 Correct 38 ms 7284 KB Output is correct
4 Correct 105 ms 19376 KB Output is correct
5 Correct 163 ms 19508 KB Output is correct
6 Correct 113 ms 20772 KB Output is correct
7 Correct 134 ms 21676 KB Output is correct
8 Correct 97 ms 19964 KB Output is correct
9 Correct 93 ms 20272 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 15 ms 2112 KB Output is correct
3 Correct 111 ms 12196 KB Output is correct
4 Correct 220 ms 15852 KB Output is correct
5 Correct 230 ms 15548 KB Output is correct
6 Correct 217 ms 15564 KB Output is correct
7 Correct 200 ms 15568 KB Output is correct
8 Correct 180 ms 15564 KB Output is correct
9 Correct 173 ms 16052 KB Output is correct
10 Correct 204 ms 16092 KB Output is correct
11 Correct 148 ms 16436 KB Output is correct
12 Correct 157 ms 17316 KB Output is correct
13 Correct 180 ms 17048 KB Output is correct
14 Correct 191 ms 16976 KB Output is correct
15 Correct 144 ms 15584 KB Output is correct
16 Correct 149 ms 15588 KB Output is correct
17 Correct 178 ms 16616 KB Output is correct
18 Correct 165 ms 17032 KB Output is correct
19 Correct 162 ms 15588 KB Output is correct
20 Correct 198 ms 17704 KB Output is correct
21 Correct 178 ms 18736 KB Output is correct
22 Correct 234 ms 18636 KB Output is correct
23 Correct 165 ms 17620 KB Output is correct
24 Correct 192 ms 17636 KB Output is correct
25 Correct 194 ms 21332 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 720 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 808 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -