oj.uz

Submission #969833

# Submission time Handle Problem Language Result Execution time Memory
969833 2024-04-25T16:15:50 Z BestCrazyNoob Highway Tolls (IOI18_highway) C++17
13 / 100
 474 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]+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) {
            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:122:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |             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 500 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 508 KB Output is correct
2 Correct 12 ms 1280 KB Output is correct
3 Correct 104 ms 8412 KB Output is correct
4 Correct 90 ms 8472 KB Output is correct
5 Correct 97 ms 8524 KB Output is correct
6 Correct 114 ms 8432 KB Output is correct
7 Correct 122 ms 8528 KB Output is correct
8 Correct 108 ms 8660 KB Output is correct
9 Correct 73 ms 8440 KB Output is correct
10 Correct 90 ms 8384 KB Output is correct
11 Correct 104 ms 9420 KB Output is correct
12 Correct 89 ms 9780 KB Output is correct
13 Correct 104 ms 9304 KB Output is correct
14 Correct 95 ms 8780 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1840 KB Output is correct
2 Correct 28 ms 3020 KB Output is correct
3 Correct 21 ms 4580 KB Output is correct
4 Correct 71 ms 13104 KB Output is correct
5 Correct 81 ms 13268 KB Output is correct
6 Correct 72 ms 13108 KB Output is correct
7 Correct 75 ms 13356 KB Output is correct
8 Correct 60 ms 13172 KB Output is correct
9 Correct 68 ms 13104 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 14 ms 1276 KB Output is correct
3 Correct 75 ms 6640 KB Output is correct
4 Runtime error 474 ms 8264 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 9 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 12 ms 856 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -