oj.uz

Submission #445959

# Submission time Handle Problem Language Result Execution time Memory
445959 2021-07-20T09:27:04 Z fammo Mousetrap (CEOI17_mousetrap) C++11
45 / 100
 930 ms 81836 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 13 ms 23808 KB Output is correct
4 Correct 13 ms 23816 KB Output is correct
5 Correct 13 ms 23756 KB Output is correct
6 Correct 15 ms 23700 KB Output is correct
7 Correct 13 ms 23812 KB Output is correct
8 Correct 13 ms 23768 KB Output is correct
9 Correct 13 ms 23756 KB Output is correct
10 Correct 13 ms 23808 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 79624 KB Output is correct
2 Correct 316 ms 74564 KB Output is correct
3 Correct 921 ms 81796 KB Output is correct
4 Correct 441 ms 55872 KB Output is correct
5 Correct 930 ms 81836 KB Output is correct
6 Correct 928 ms 81820 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 13 ms 23808 KB Output is correct
4 Correct 13 ms 23816 KB Output is correct
5 Correct 13 ms 23756 KB Output is correct
6 Correct 15 ms 23700 KB Output is correct
7 Correct 13 ms 23812 KB Output is correct
8 Correct 13 ms 23768 KB Output is correct
9 Correct 13 ms 23756 KB Output is correct
10 Correct 13 ms 23808 KB Output is correct
11 Incorrect 13 ms 23812 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 13 ms 23808 KB Output is correct
4 Correct 13 ms 23816 KB Output is correct
5 Correct 13 ms 23756 KB Output is correct
6 Correct 15 ms 23700 KB Output is correct
7 Correct 13 ms 23812 KB Output is correct
8 Correct 13 ms 23768 KB Output is correct
9 Correct 13 ms 23756 KB Output is correct
10 Correct 13 ms 23808 KB Output is correct
11 Correct 364 ms 79624 KB Output is correct
12 Correct 316 ms 74564 KB Output is correct
13 Correct 921 ms 81796 KB Output is correct
14 Correct 441 ms 55872 KB Output is correct
15 Correct 930 ms 81836 KB Output is correct
16 Correct 928 ms 81820 KB Output is correct
17 Incorrect 13 ms 23812 KB Output isn't correct
18 Halted 0 ms 0 KB -