Submission #1096442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096442		Mike_Vu	Mousetrap (CEOI17_mousetrap)	C++14	25 / 100	586 ms	73428 KiB

mousetrap

#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
• Subtask 2: 25 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35