oj.uz

Submission #538998

# Submission time Handle Problem Language Result Execution time Memory
538998 2022-03-18T07:29:06 Z syl123456 Mousetrap (CEOI17_mousetrap) C++17
20 / 100
 213 ms 524288 KB 
#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wparentheses"
#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
#define random random_device rd; mt19937 rng(rd())
using namespace std;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
    return i << j.first << ' ' << j.second;
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
    i << '{' << j.size() << ':';
    for (T ii : j) i << ' ' << ii;
    return i << '}';
}
void Debug(bool _split) {}
template<typename T1, typename ...T2>
void Debug(bool _split, T1 x, T2 ...args) {
    if (_split)
        cerr << ", ";
    cerr << x, Debug(true, args...);
}
template<typename T>
void Debuga(T *i, int n) {
    cerr << '[';
    for (int j = 0; j < n; ++j) cerr << i[j] << " ]"[j == n - 1];
    cerr << endl;
}
#ifdef SYL
#define debug(args...) cerr << "\u001b[35mLine(" << __LINE__ << ") -> [" << #args << "] is [", Debug(false, args), cerr << "]\u001b[0m" << endl
#define debuga(i) cerr << "\u001b[35mLine(" << __LINE__ << ") -> [" << #i << "] is ", Debuga(i, sizeof(i) / sizeof(typeid(*i).name())), cerr << "\u001b[0m"
#else
#define debug(args...) void(0)
#define debuga(i) void(0)
#endif
typedef long long ll;
typedef pair<int, int> pi;
const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;

vector<vector<int>> g, dp, pa;
vector<int> c, d, dep;
int n, s, t;

void dfs1(int i, int p, int _d) {
    pa[i][0] = p, dep[i] = i == s ? 0 : dep[p] + 1;
    if (i == t)
        return c[i] = _d, d[i] = 0, void();
    c[i] = _d + g[i].size() - (i != s);
    for (int j : g[i])
        if (j != p)
            dfs1(j, i, c[i]);
}

int lca(int i, int j) {
    if (dep[i] < dep[j])
        swap(i, j);
    for (int x = lg - 1; ~x; --x)
        if (dep[pa[i][x]] >= dep[j])
            i = pa[i][x];
    for (int x = lg - 1; ~x; --x)
        if (pa[i][x] != pa[j][x])
            i = pa[i][x], j = pa[j][x];
    return i == j ? i : pa[i][0];
}

void build() {
    for (int i = 1; i < lg; ++i)
        for (int j = 0; j < n; ++j)
            pa[j][i] = pa[pa[j][i - 1]][i - 1];
    for (int i = 0; i < n; ++i)
        if (~dep[i]) {
            int x = lca(i, t);
            d[i] = c[i] + c[pa[t][0]] - c[x] - (x != s ? c[pa[x][0]] : 0) - dep[t] + dep[x];
        }
}

bool dfs2(int i, int p) {
    if (i == t)
        return fill(all(dp[i]), d[i]), true;
    vector<vector<int>> v(n + 1);
    int ch = -1;
    for (int j : g[i])
        if (j != p) {
            if (dfs2(j, i)) {
                ch = j;
                continue;
            }
            for (int x = 0; x <= n; ++x)
                v[x].push_back(dp[j][x]);
        }
    for (int j = 0; j <= n; ++j)
        sort(all(v[j]), [](int x, int y) {return x > y;});
    int sz = v[0].size();
    for (int j = 0; j <= n; ++j) {
        dp[i][j] = inf;
        for (int x = 0; x <= j; ++x) {
            if (j - x + 1 > n || x > sz)
                continue;
            if (x == sz) {
                if (~ch)
                    dp[i][j] = min(dp[i][j], x + dp[ch][j - x + 1]);
                else
                    dp[i][j] = min(dp[i][j], d[i]);
                break;
            }
            if (~ch)
                dp[i][j] = min(dp[i][j], max(x + dp[ch][j - x + 1], v[j - x + 1][x]));
            else
                dp[i][j] = min(dp[i][j], v[j - x + 1][x]);
        }
    }
    return ch != -1;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> t >> s;
    if (s == t)
        return cout << 0, 0;
    --s, --t;
    g.resize(n), dp.assign(n, vector<int>(n + 1));
    d.resize(n), dep.assign(n, -1), c.resize(n), pa.assign(n, vector<int>(lg));
    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        g[x].push_back(y), g[y].push_back(x);
    }
    dfs1(s, s, 0);
    build();
    dfs2(s, -1);
    cout << dp[s][1];
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 43 ms 5076 KB Output is correct
13 Incorrect 44 ms 4992 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Runtime error 213 ms 524288 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -