oj.uz

Submission #578431

# Submission time Handle Problem Language Result Execution time Memory
578431 2022-06-16T20:35:18 Z vladislav11 Mousetrap (CEOI17_mousetrap) C++14
0 / 100
 317 ms 72360 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -