oj.uz

Submission #432719

# Submission time Handle Problem Language Result Execution time Memory
432719 2021-06-18T12:47:32 Z 2qbingxuan Towns (IOI15_towns) C++17
61 / 100
 28 ms 372 KB 
#include "towns.h"
#include <bits/stdc++.h>
#ifdef local
#define debug(a...) qqbx(#a, a)
#define pary(a...) danb(#a, a)
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\e[1;32m(" << s << ") = ("), ..., (std::cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename T> void danb(const char *s, T L, T R) {
    std::cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        std::cerr << (f++ ? ", " : "") << *L;
    std::cerr << " ]\e[0m\n";
}
#else
#define debug(...) ((void)0)
#define pary(...) ((void)0)
#define safe ((void)0)
#endif // local
#define all(v) begin(v),end(v)

using namespace std;

map<pair<int,int>,int> asked;
int ask(int a, int b) {
    if (a == b) return 0;
    if (a > b) swap(a, b);
    if (asked.count({ a, b })) return asked[{ a, b }];
    return asked[{ a, b }] = getDistance(a, b);
}
int hubDistance(int N, int sub) {
    asked.clear();
    assert (1 <= sub && sub <= 6);
    int A = 0, B = 0;
    for (int i = 0; i < N; i++) {
        if (ask(0, i) > ask(0, A)) {
            A = i;
        }
    }
    for (int i = 0; i < N; i++) {
        if (ask(A, i) > ask(A, B)) {
            B = i;
        }
    }
    debug(asked.size(), N*2-3);
    int R = ask(A, B);
    debug(A, B, R);
    vector<tuple<int,int,int>> leaf(N);
    for (int i = 0; i < N; i++) {
        int AB = ask(A, B);
        int AI = ask(A, i);
        int BI = ask(B, i);
        assert ((AB + abs(AI - BI)) % 2 == 0);
        R = min(R, (AB + abs(AI - BI)) / 2);
        leaf[i] = { (AB + AI - BI) / 2, (AB + abs(AI - BI)) / 2, i };
    }
    sort(all(leaf));
    if (sub <= 2) return R;
    bool bal = false;
    for (int i = 0, j = 0; i < N; i = j) {
        for (j = i; j < N; j++) if (get<0>(leaf[i]) != get<0>(leaf[j])) break;
        int RR = get<1>(leaf[i]);
        if (i <= N / 2 && N - j <= N / 2 && RR == R) {
            if (sub == 4) {
                if (j-i <= N/2)
                    bal = true;
                break;
            }
            vector<int> ids;
            for (int t = i; t < j; t++)
                ids.push_back(get<2>(leaf[t]));

            auto sameSubtree = [&](int x, int y) {
                int Lx = (ask(A, x) + ask(x, B) - ask(A, B)) / 2;
                int Ly = (ask(A, y) + ask(y, B) - ask(A, B)) / 2;
                return ask(x, y) != Lx + Ly;
            };
            vector<int> stk;
            for (int x: ids) {
                if (stk.empty()) {
                    stk.push_back(x);
                } else {
                    if (sameSubtree(x, stk.back()))
                        stk.push_back(x);
                    else
                        stk.pop_back();
                }
            }
            if (stk.empty()) {
                bal = true;
            } else {
                int cnt = 0;
                for (int x: ids)
                    if (sameSubtree(x, stk.back()))
                        ++cnt;
                if (cnt <= N / 2)
                    bal = true;
            }
            break;
        }
    }
    debug(bal);
    debug(asked.size());
    return bal ? R : -R;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 332 KB Output is correct
2 Correct 15 ms 360 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 20 ms 352 KB Output is correct
5 Correct 20 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 360 KB Output is correct
2 Correct 14 ms 332 KB Output is correct
3 Correct 22 ms 332 KB Output is correct
4 Correct 19 ms 332 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 368 KB Output is correct
2 Correct 22 ms 372 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 22 ms 372 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 360 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 372 KB Output is correct
2 Correct 23 ms 332 KB Output is correct
3 Correct 28 ms 372 KB Output is correct

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -