oj.uz

Submission #969840

# Submission time Handle Problem Language Result Execution time Memory
969840 2024-04-25T16:26:51 Z BestCrazyNoob Highway Tolls (IOI18_highway) C++17
51 / 100
 140 ms 13616 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]+1) / 2);
        // centroid becomes root
        dfs(centroid, -1);
        if (sz[centroid] == 2) {
            for (auto [c, i]: adj[centroid]) {
                if (good[c]) {
                    answer(centroid, c);
                    return;
                }
            }
            assert(false);
        }
        vector<int> w(M, false);
        int cut = 0, currSz = 0;
        while (currSz < (sz[centroid]-1) / 2) {
            auto [c, i] = adj[centroid][cut];
            if (!good[c]) {
                cut++;
                continue;
            }
            w[i] = true;
            set_b(c, centroid, w);
            currSz += sz[c];
            cut++;
        }
        assert(currSz > 0 && currSz < sz[centroid]);
        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:128:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |             for (int i = cut; i < adj[centroid].size(); i++) {
      |                               ~~^~~~~~~~~~~~~~~~~~~~~~

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 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 14 ms 1284 KB Output is correct
3 Correct 104 ms 8404 KB Output is correct
4 Correct 90 ms 8484 KB Output is correct
5 Correct 121 ms 8632 KB Output is correct
6 Correct 87 ms 8432 KB Output is correct
7 Correct 103 ms 8696 KB Output is correct
8 Correct 91 ms 8408 KB Output is correct
9 Correct 96 ms 8572 KB Output is correct
10 Correct 114 ms 8508 KB Output is correct
11 Correct 116 ms 9188 KB Output is correct
12 Correct 124 ms 10024 KB Output is correct
13 Correct 101 ms 9312 KB Output is correct
14 Correct 107 ms 9008 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1736 KB Output is correct
2 Correct 23 ms 3152 KB Output is correct
3 Correct 28 ms 4576 KB Output is correct
4 Correct 82 ms 13040 KB Output is correct
5 Correct 97 ms 13568 KB Output is correct
6 Correct 80 ms 13108 KB Output is correct
7 Correct 101 ms 13108 KB Output is correct
8 Correct 78 ms 13100 KB Output is correct
9 Correct 101 ms 13616 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 508 KB Output is correct
2 Correct 12 ms 1284 KB Output is correct
3 Correct 70 ms 6620 KB Output is correct
4 Correct 88 ms 8392 KB Output is correct
5 Correct 132 ms 8396 KB Output is correct
6 Correct 105 ms 8528 KB Output is correct
7 Correct 139 ms 8628 KB Output is correct
8 Correct 120 ms 8384 KB Output is correct
9 Correct 83 ms 8880 KB Output is correct
10 Correct 75 ms 8444 KB Output is correct
11 Correct 72 ms 8672 KB Output is correct
12 Correct 97 ms 10116 KB Output is correct
13 Correct 74 ms 9412 KB Output is correct
14 Correct 99 ms 9728 KB Output is correct
15 Correct 123 ms 8620 KB Output is correct
16 Correct 140 ms 8260 KB Output is correct
17 Correct 126 ms 9660 KB Output is correct
18 Correct 72 ms 9160 KB Output is correct
19 Correct 92 ms 8396 KB Output is correct
20 Correct 98 ms 10212 KB Output is correct
21 Correct 68 ms 9760 KB Output is correct
22 Correct 80 ms 10432 KB Output is correct
23 Correct 66 ms 9460 KB Output is correct
24 Correct 79 ms 9676 KB Output is correct
25 Correct 94 ms 12756 KB Output is correct

Subtask #5
0 / 18.0

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