Submission #93058

#	Time	Username	Problem	Language	Result	Execution time	Memory
93058		Kastanda	Mousetrap (CEOI17_mousetrap)	C++11	25 / 100	1275 ms	61176 KiB

mousetrap

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 1000006;
int n, s, t, def[N], dp[N];
bool is[N];
vector < int > Adj[N];
void DFS(int v, int p)
{
    if (v == t)
    {
        Adj[v].clear();
        is[v] = 1;
        return ;
    }
    for (int i = 0; i < Adj[v].size(); i++)
        if (Adj[v][i] == p)
        {
            swap(Adj[v][i], Adj[v].back());
            Adj[v].pop_back();
        }
    for (int i = 0; i < Adj[v].size(); i++)
    {
        DFS(Adj[v][i], v);
        is[v] |= is[Adj[v][i]];
        if (is[Adj[v][i]])
            swap(Adj[v][0], Adj[v][i]);
    }
    if (is[v])
        def[v] = def[Adj[v][0]] + (int)Adj[v].size() - 1;
    return ;
}
void DFS2(int v, int p)
{
    if (!Adj[v].size())
    {
        dp[v] = 0;
        return ;
    }
    vector < int > A;
    for (int &u : Adj[v])
    {
        DFS2(u, v);
        if (!is[u])
            A.pb(dp[u]);
    }
    sort(A.begin(), A.end());
    reverse(A.begin(), A.end());
    A.pb(0);
    if (!is[v])
    {
        dp[v] = (int)Adj[v].size() + A[1];
        return ;
    }
    else
    {
        int pt = Adj[v][0];
        if (Adj[v].size() == 1)
        {
            dp[v] = dp[pt];
            return ;
        }

        int best_choice = 1e9;

        //best_choice = (int)Adj[v].size() + 1 + A[0] + def[pt];

        int maxx = dp[pt];
        if (A.size() > 2)
            maxx = max(maxx, A[1] + (int)Adj[v].size() - 2 + def[pt]);
        best_choice = min(best_choice, 1 + maxx);

        best_choice = min(best_choice, max(dp[pt], A[0] + (int)Adj[v].size() - 1 + def[pt]));
        dp[v] = best_choice;
    }
}
int main()
{
    scanf("%d%d%d", &n, &t, &s);
    for (int i = 1; i <= n - 1; i++)
    {
        int v, u;
        scanf("%d%d", &v, &u);
        Adj[v].pb(u);
        Adj[u].pb(v);
    }
    DFS(s, 0);
    DFS2(s, 0);
    printf("%d\n", dp[s]);
    return (0);
}

Compilation message (stderr)

mousetrap.cpp: In function 'void DFS(int, int)':
mousetrap.cpp:16:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < Adj[v].size(); i++)
                     ~~^~~~~~~~~~~~~~~
mousetrap.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < Adj[v].size(); i++)
                     ~~^~~~~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &t, &s);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &v, &u);
         ~~~~~^~~~~~~~~~~~~~~~

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