oj.uz

Submission #969815

# Submission time Handle Problem Language Result Execution time Memory
969815 2024-04-25T15:56:00 Z BestCrazyNoob Highway Tolls (IOI18_highway) C++17
13 / 100
 427 ms 13356 KB 
#include "highway.h"
#include <vector>
#include <cassert>

using namespace std;
using ll = long long;

struct Edge {
    int d, i;
};

vector<vector<Edge>> adj;
vector<bool> good;
vector<int> sz;

void dfs(int curr, int prev) {
    sz[curr] = 1;
    for (auto [c, i]: adj[curr]) {
        if (c == prev || !good[c]) continue;
        dfs(c, curr);
        sz[curr] += sz[c];
    }
}

int get_c(int curr, int prev, int tar) {
    for (auto [c, i]: adj[curr]) {
        if (c == prev || !good[c]) continue;
        if (sz[c] >= tar) return get_c(c, curr, tar);
    }
    return curr;
}

void set_bad(int curr, int prev) {
    good[curr] = false;
    for (auto [c, i]: adj[curr]) {
        if (c == prev) continue;
        set_bad(c, curr);
    }
}

void set_b(int curr, int prev, vector<int> &w) {
    for (auto [c, i]: adj[curr]) {
        if (c == prev || !good[c]) continue;
        w[i] = true;
        set_b(c, curr, w);
    }
}

void add_candidates(int curr, int prev, int d, vector<Edge> &tars) {
    for (auto [c, i]: adj[curr]) {
        if (c == prev || !good[c]) continue;
        if (d == 1) tars.push_back({c, i});
        else add_candidates(c, curr, d-1, tars);
    }
}

// guaranteed d >= 1
int find_one(int centroid, vector<Edge> sources, int d, ll distA) {
    vector<Edge> candidates;
    for (auto [c, i]: sources) {
        if (d == 1) candidates.push_back({c, i});
        else add_candidates(c, centroid, d-1, candidates);
    }
    int low = 0, high = candidates.size();
    while (low+1 < high) {
        int mid = (low+high)/2;
        vector<int> w(adj.size()-1, false);
        for (int i = low; i < mid; i++) w[candidates[i].i] = true;
        if (ask(w) != distA) high = mid;
        else low = mid;
    }
    return candidates[low].d;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    const int M = U.size();

    assert(M == N-1); // TODO

    adj.resize(N);
    good.resize(N, true);
    sz.resize(N);

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

    // distance between S and T
    ll dist = ask(vector<int>(M, 0)) / A;
    // tree is always rooted at the centroid
    int centroid = 0;

    while (true) {
        dfs(centroid, -1);
        centroid = get_c(centroid, -1, sz[centroid] / 2);
        // centroid becomes root
        dfs(centroid, -1);
        vector<int> w(M, false);
        int cut = 0, currSz = 0;
        while (currSz < (sz[centroid]-1) / 2) {
            w[adj[centroid][cut].i] = true;
            set_b(adj[centroid][cut].d, centroid, w);
            currSz += sz[adj[centroid][cut].d];
            cut++;
        }
        ll res = ask(w);
        if (res == A*dist) {
            for (int i = 0; i < cut; i++) {
                set_bad(adj[centroid][i].d, centroid);
            }
        } else if (res == B*dist) {
            for (int i = cut; i < adj[centroid].size(); i++) {
                set_bad(adj[centroid][i].d, centroid);
            }
        } else {
            const int x = (res - A*dist) / (B - A);
            const int y = dist - x;
            answer(
                x == 0 ? centroid : find_one(centroid, vector<Edge>(adj[centroid].begin(), adj[centroid].begin() + cut), x, dist*A),
                y == 0 ? centroid : find_one(centroid, vector<Edge>(adj[centroid].begin() + cut, adj[centroid].end()), y, dist*A)
            );
            return;
        }
    }
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:113:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             for (int i = cut; i < adj[centroid].size(); i++) {
      |                               ~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
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 340 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Runtime error 1 ms 432 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 12 ms 1276 KB Output is correct
3 Correct 90 ms 8424 KB Output is correct
4 Correct 89 ms 8476 KB Output is correct
5 Correct 82 ms 8484 KB Output is correct
6 Correct 83 ms 8684 KB Output is correct
7 Correct 85 ms 8436 KB Output is correct
8 Correct 127 ms 8404 KB Output is correct
9 Correct 93 ms 8440 KB Output is correct
10 Correct 87 ms 8384 KB Output is correct
11 Correct 124 ms 9196 KB Output is correct
12 Correct 101 ms 9780 KB Output is correct
13 Correct 114 ms 9308 KB Output is correct
14 Correct 76 ms 8772 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1736 KB Output is correct
2 Correct 24 ms 3036 KB Output is correct
3 Correct 26 ms 4576 KB Output is correct
4 Correct 54 ms 13108 KB Output is correct
5 Correct 90 ms 13356 KB Output is correct
6 Correct 73 ms 13104 KB Output is correct
7 Correct 72 ms 13176 KB Output is correct
8 Correct 77 ms 13120 KB Output is correct
9 Correct 67 ms 13108 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 508 KB Output is correct
2 Correct 11 ms 1452 KB Output is correct
3 Correct 72 ms 6872 KB Output is correct
4 Runtime error 427 ms 8016 KB Execution killed with signal 13
5 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 756 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 2 ms 752 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -