oj.uz

Submission #1096442

# Submission time Handle Problem Language Result Execution time Memory
1096442 2024-10-04T12:47:32 Z Mike_Vu Mousetrap (CEOI17_mousetrap) C++14
25 / 100
 586 ms 73428 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

const int maxn = 1e6+5;
int n, s, t;
vector<int> a[maxn];
priority_queue<int> q;
int h[maxn], sumpath = 0, sumnxt = 0;

int calcost(int u, int p) {
    if ((int)a[u].size() < 3) {
        //cannot continue
        return (int)a[u].size();
    }
    int ma1 = 0, ma2 = 0;
    for (int v : a[u]) {
        if (v == p) continue;
        int val = calcost(v, u);
        if (val > ma1){
            ma2 = ma1;
            ma1 = val;
        }
        else if (val > ma2){
            ma2 = val;
        }
    }
//    cout << "calcost " << u << ' ' << ma2+(int)a[u].size()-1 << "\n";
    return ma2+(int)a[u].size()-1;
}

bool dfs(int u, int p) {
    if (u == t) return 1;
    //check
    int nxt = -1;
    for (int v : a[u]) {
        if (v == p) continue;
        h[v] = h[u]+1;
        if (dfs(v, u)) {
            nxt = v;
        }
    }
    if (nxt == -1) return 0;
    for (int v : a[u]) {
        if (v == nxt || v == p) continue;
        int val = calcost(v, u);
        q.push(val+(int)a[u].size()-3+(u==s)+h[u]+sumnxt);
    }
    sumnxt += a[u].size()-2+(u==s);
    if (!q.empty()) {
        q.pop();
        sumpath++;
    }
    return 1;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    cin >> n >> t >> s;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        a[u].pb(v);
        a[v].pb(u);
    }
    //block all except the mouse's chosen path
    h[s] = 0;
    dfs(s, -1);
    cout << (q.empty() ? sumpath : q.top());
}
/*
10 1 2
1 2
2 3
2 4
3 9
3 5
4 7
4 6
6 8
7 10
*/

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23900 KB Output is correct
2 Correct 10 ms 23896 KB Output is correct
3 Correct 14 ms 23900 KB Output is correct
4 Correct 10 ms 23952 KB Output is correct
5 Correct 10 ms 23924 KB Output is correct
6 Correct 10 ms 23944 KB Output is correct
7 Correct 13 ms 23896 KB Output is correct
8 Incorrect 14 ms 23760 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 72376 KB Output is correct
2 Correct 215 ms 67568 KB Output is correct
3 Correct 578 ms 73300 KB Output is correct
4 Correct 271 ms 48464 KB Output is correct
5 Correct 586 ms 73312 KB Output is correct
6 Correct 576 ms 73428 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23900 KB Output is correct
2 Correct 10 ms 23896 KB Output is correct
3 Correct 14 ms 23900 KB Output is correct
4 Correct 10 ms 23952 KB Output is correct
5 Correct 10 ms 23924 KB Output is correct
6 Correct 10 ms 23944 KB Output is correct
7 Correct 13 ms 23896 KB Output is correct
8 Incorrect 14 ms 23760 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23900 KB Output is correct
2 Correct 10 ms 23896 KB Output is correct
3 Correct 14 ms 23900 KB Output is correct
4 Correct 10 ms 23952 KB Output is correct
5 Correct 10 ms 23924 KB Output is correct
6 Correct 10 ms 23944 KB Output is correct
7 Correct 13 ms 23896 KB Output is correct
8 Incorrect 14 ms 23760 KB Output isn't correct
9 Halted 0 ms 0 KB -