oj.uz

Submission #93055

# Submission time Handle Problem Language Result Execution time Memory
93055 2019-01-06T10:33:27 Z Kastanda Mousetrap (CEOI17_mousetrap) C++11
25 / 100
 1454 ms 74548 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct
3 Correct 22 ms 23800 KB Output is correct
4 Correct 24 ms 23800 KB Output is correct
5 Incorrect 23 ms 23800 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 72824 KB Output is correct
2 Correct 426 ms 67980 KB Output is correct
3 Correct 1454 ms 74428 KB Output is correct
4 Correct 631 ms 48888 KB Output is correct
5 Correct 1184 ms 74548 KB Output is correct
6 Correct 1153 ms 74360 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct
3 Correct 22 ms 23800 KB Output is correct
4 Correct 24 ms 23800 KB Output is correct
5 Incorrect 23 ms 23800 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct
3 Correct 22 ms 23800 KB Output is correct
4 Correct 24 ms 23800 KB Output is correct
5 Incorrect 23 ms 23800 KB Output isn't correct
6 Halted 0 ms 0 KB -