Submission #578431

#	Time	Username	Problem	Language	Result	Execution time	Memory
578431		vladislav11	Mousetrap (CEOI17_mousetrap)	C++14	0 / 100	317 ms	72360 KiB

mousetrap

#include <bits/stdc++.h>

using namespace std;

int n, m, t, ans;
vector< vector<int> > grp;
vector<int> path;

bool dfs_path ( int v, int p )
{
    if ( v == t )
        return true;

    for ( auto& to : grp[v] )
    if ( to != p && dfs_path( to, v ) )
    {
        path[v] = to;
        return true;
    }

    return false;
}

int dfs1_ans ( int v, int p )
{
    vector<int> posib;

    for ( auto& to : grp[v] )
    if ( to != p && to != path[v] )
        posib.push_back( dfs1_ans( to, v ) );

    if ( posib.size() == 0 )
        return 0;

    if ( posib.size() == 1 )
        return 1;

    int cnt = posib.size();

    return posib[cnt-2] + cnt-1 + 1;
}

void dfs2_ans ( int v, int p )
{
    if ( v == t )
        return;

    ans += grp[v].size()-2;

    dfs2_ans( path[v], v );
}

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

    cin >> n >> t >> m;

    grp.assign( n+1, vector<int>() );

    for ( int i=1; i<n; i++ )
    {
        int u, v;
        cin >> u >> v;

        grp[u].push_back( v );
        grp[v].push_back( u );
    }

    if ( m == t )
    {
        cout << 0;
        return 0;
    }

    path.assign( n+1, -1 );
    dfs_path( m, -1 );

    /*for ( int i=1; i<=n; i++ )
        cout << path[i] << ' ';
    cout << '\n';*/

    ans += dfs1_ans( m, -1 );

    dfs2_ans( path[m], m );

    cout << ans;

    return 0;
}

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