제출 #1033276

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1033276		amine_aroua	Mousetrap (CEOI17_mousetrap)	C++17	0 / 100	692 ms	77264 KiB

mousetrap

#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] = 1;
    dp[m] = 0;
    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
• Subtask 2: 0 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35