oj.uz

Submission #559178

# Submission time Handle Problem Language Result Execution time Memory
559178 2022-05-09T13:08:14 Z fatemetmhr Mousetrap (CEOI17_mousetrap) C++17
25 / 100
 684 ms 60152 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define pb       push_back

const int maxn5 = 1e6 + 10;

int tale, mo, dp[maxn5];
int ans = 0, htotale[maxn5];
vector <int> adj[maxn5];

inline bool dfs(int v, int par){
    if(v == tale){
        dp[v] = 0;
        htotale[v] = 0;
        return true;
    }
    int mx = 0, smx = 0;
    int z = -1;
    for(auto u : adj[v]) if(u != par){
        bool re = dfs(u, v);
        if(re){
            z = u;
        }
        if(dp[u] >= mx){
            smx = mx;
            mx = dp[u];
        }
        else
            smx = max(smx, dp[u]);
    }
    if(z == -1){
        dp[v] = smx + adj[v].size() - 1;
        //cout << "false " << v << ' ' << dp[v] << endl;
        return false;
    }

    mx = smx = 0;
    for(auto u : adj[v]) if(u != par && u != z){
        if(dp[u] >= mx){
            smx = mx;
            mx = dp[u];
        }
        else
            smx = max(smx, dp[u]);
    }

    dp[v] = smx + adj[v].size() - 2 + htotale[z];
    if(v == mo)
        dp[v]++;
    htotale[v] = htotale[z] + adj[v].size() - 2;
    ans = max(ans, dp[v]);
    //cout << v << ' ' << dp[v] << ' ' << htotale[v] << ' ' << smx << ' ' << mx << endl;
    return true;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n, a, b; cin >> n >> a >> b;
    a--; b--;
    mo = b;
    tale = a;
    for(int i = 0; i < n - 1; i++){
        int a, b; cin >> a >> b;
        a--; b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }

    assert(a != b);

    if(a == b)
        return cout << 0 << endl, 0;

    dfs(mo, -1);
    cout << ans << endl;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23784 KB Output is correct
3 Correct 12 ms 23776 KB Output is correct
4 Correct 12 ms 23736 KB Output is correct
5 Incorrect 12 ms 23764 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 58928 KB Output is correct
2 Correct 251 ms 55500 KB Output is correct
3 Correct 681 ms 60116 KB Output is correct
4 Correct 330 ms 41964 KB Output is correct
5 Correct 684 ms 60128 KB Output is correct
6 Correct 682 ms 60152 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23784 KB Output is correct
3 Correct 12 ms 23776 KB Output is correct
4 Correct 12 ms 23736 KB Output is correct
5 Incorrect 12 ms 23764 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23784 KB Output is correct
3 Correct 12 ms 23776 KB Output is correct
4 Correct 12 ms 23736 KB Output is correct
5 Incorrect 12 ms 23764 KB Output isn't correct
6 Halted 0 ms 0 KB -