oj.uz

Submission #1033272

# Submission time Handle Problem Language Result Execution time Memory
1033272 2024-07-24T15:44:52 Z amine_aroua Mousetrap (CEOI17_mousetrap) C++17
0 / 100
 702 ms 77136 KB 
#include<bits/stdc++.h>
using namespace std;
vector<int> dp;
vector<vector<int>> adj;
vector<int> depth;
void dfs(int x , int p)
{
    for(auto u : adj[x])
    {
        if(u == p)
            continue;
        depth[u] = depth[x] + 1;
        dp[u] = dp[x] + (int)adj[x].size() - 2;
        dfs(u,x);
    }
}
int main()
{
    int n , t , m;
    cin>>n>>t>>m;
    adj.assign(n + 1 , {});
    dp.assign(n + 1 , 2e9);
    depth = dp;
    for(int i = 0 ; i < n - 1 ; i++)
    {
        int u , v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    depth[m] = 0;
    dp[m] = 1;
    dfs(m , t);
    int ans = 2e9;
    for(int i = 1 ; i <= n ; i++)
    {
        if(i == t)
            continue;
        if((int)adj[i].size() - 1 + dp[i] <= depth[i])
        {
            ans = min(ans , (int)adj[i].size() - 2 + dp[i] + depth[i]);
        }
        if((int)adj[i].size() == 1)
        {
            ans = min(ans , depth[i] + (int)adj[i].size() - 2 + dp[i]);
        }
    }
    cout<<ans<<'\n';
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 76372 KB Output is correct
2 Correct 407 ms 68756 KB Output is correct
3 Incorrect 702 ms 77136 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -