oj.uz

Submission #93074

# Submission time Handle Problem Language Result Execution time Memory
93074 2019-01-06T11:35:36 Z Kastanda Mousetrap (CEOI17_mousetrap) C++11
45 / 100
 1503 ms 62100 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, int spare = 0)
{
    if (!Adj[v].size())
    {
        dp[v] = 0;
        return ;
    }
    vector < int > A;
    for (int &u : Adj[v])
        if (!is[u])
        {
            DFS2(u, v);
            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)
        {
            DFS2(pt, v, spare + 1);
            dp[v] = dp[pt];
            return ;
        }
        if (spare >= (int)Adj[v].size() - 1)
        {
            DFS2(pt, v, spare - (int)Adj[v].size() + 1);
            dp[v] = dp[pt] + (int)Adj[v].size() - 1;

            DFS2(pt, v, spare + 1);
            dp[v] = min(dp[v], max(dp[pt], A[0] + (int)Adj[v].size() - 1 + def[pt]));
            return ;
        }

        int best_choice = 1e9;

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

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

        DFS2(pt, v, spare + 1);
        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:91: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:95: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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 23 ms 23804 KB Output is correct
3 Correct 22 ms 23800 KB Output is correct
4 Correct 22 ms 23800 KB Output is correct
5 Correct 22 ms 23848 KB Output is correct
6 Correct 23 ms 23800 KB Output is correct
7 Correct 22 ms 23844 KB Output is correct
8 Correct 23 ms 24056 KB Output is correct
9 Correct 23 ms 23800 KB Output is correct
10 Correct 22 ms 23800 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 60472 KB Output is correct
2 Correct 424 ms 56756 KB Output is correct
3 Correct 1503 ms 62032 KB Output is correct
4 Correct 683 ms 44024 KB Output is correct
5 Correct 1451 ms 62100 KB Output is correct
6 Correct 1462 ms 62064 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 23 ms 23804 KB Output is correct
3 Correct 22 ms 23800 KB Output is correct
4 Correct 22 ms 23800 KB Output is correct
5 Correct 22 ms 23848 KB Output is correct
6 Correct 23 ms 23800 KB Output is correct
7 Correct 22 ms 23844 KB Output is correct
8 Correct 23 ms 24056 KB Output is correct
9 Correct 23 ms 23800 KB Output is correct
10 Correct 22 ms 23800 KB Output is correct
11 Correct 22 ms 23800 KB Output is correct
12 Correct 36 ms 23928 KB Output is correct
13 Correct 25 ms 23928 KB Output is correct
14 Correct 24 ms 24056 KB Output is correct
15 Correct 23 ms 24056 KB Output is correct
16 Correct 28 ms 23928 KB Output is correct
17 Incorrect 26 ms 23800 KB Output isn't correct
18 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 23 ms 23804 KB Output is correct
3 Correct 22 ms 23800 KB Output is correct
4 Correct 22 ms 23800 KB Output is correct
5 Correct 22 ms 23848 KB Output is correct
6 Correct 23 ms 23800 KB Output is correct
7 Correct 22 ms 23844 KB Output is correct
8 Correct 23 ms 24056 KB Output is correct
9 Correct 23 ms 23800 KB Output is correct
10 Correct 22 ms 23800 KB Output is correct
11 Correct 482 ms 60472 KB Output is correct
12 Correct 424 ms 56756 KB Output is correct
13 Correct 1503 ms 62032 KB Output is correct
14 Correct 683 ms 44024 KB Output is correct
15 Correct 1451 ms 62100 KB Output is correct
16 Correct 1462 ms 62064 KB Output is correct
17 Correct 22 ms 23800 KB Output is correct
18 Correct 36 ms 23928 KB Output is correct
19 Correct 25 ms 23928 KB Output is correct
20 Correct 24 ms 24056 KB Output is correct
21 Correct 23 ms 24056 KB Output is correct
22 Correct 28 ms 23928 KB Output is correct
23 Incorrect 26 ms 23800 KB Output isn't correct
24 Halted 0 ms 0 KB -