Submission #445959

#	Time	Username	Problem	Language	Result	Execution time	Memory
445959		fammo	Mousetrap (CEOI17_mousetrap)	C++11	45 / 100	930 ms	81836 KiB

mousetrap

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")

#define int long long

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
#define X first
#define Y second
#define pb push_back
#define fastio ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define rndom mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
//#define endl '\n'
const int  N = 1000 * 1000 + 5, inf = LLONG_MAX;
int n, m, t, par[N];
vector<int>adj[N];
int dp[N], r = -1, c = 1;
bool mark[N];
void dfs(int v, int p){
    pii mx = {0, 0}; int ch = 0;
    vector<int>vec;
    for(int u : adj[v])if(u!=p && !mark[u]){
        ch ++;
        dfs(u, v);
        if(v == r){
            vec.pb(dp[u]);
            continue;
        }
        if(dp[u] > mx.X){
            pii tmp = {dp[u], mx.X};
            mx = tmp;
        }else if(dp[u] > mx.Y){
            mx.Y = dp[u];
        }
    }
    if(v == r){
        while((int)vec.size() <= c)vec.pb(0);
        sort(vec.begin(), vec.end(), greater<int>());
        dp[v] = vec[c-1] + ch;
        return;
    }
    if(ch == 0)return;
    if(ch == 1){dp[v] = 1; return;}
    dp[v] = ch + mx.Y;
    return;
}
void path(int v, int p){
    par[v] = p;
    for(int u : adj[v])if(u!=p){
        path(u,v);
    }return;
}
int32_t main(){
    ///auto t = clock();
    fastio;
    cin >> n >> t >> m; m--; t --;
    for(int i = 0; i < n -1; i ++){
        int u, v;
        cin >> u >> v;
        v--; u --;
        adj[u].pb(v); adj[v].pb(u);
    }
    path(m,-1);
    mark[m] = 1;
    vector<int>p;
    int cur = t;
    do{
        //cout << "mark " << cur +1 << endl;
        mark[cur] = 1;
        p.pb(cur);
        cur = par[cur];
    }while(cur != -1);
    reverse(p.begin(), p.end());
    p.pop_back();
    int ans = 0;
    for(int u : p){
        //cout << "dfs " << u+1 << ": ";
        r = u;
        c++;
        dfs(u, -1);
        //cout << dp[u] << endl;
        ans += dp[u];
    }
    cout << ans << endl;
    ///cout << clock() - t << "ms" << endl;
    return 0;

}

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35