Submission #54228

#	Time	Username	Problem	Language	Result	Execution time	Memory
54228		SpaimaCarpatilor	Mousetrap (CEOI17_mousetrap)	C++17	100 / 100	1212 ms	250968 KiB

mousetrap

#include<bits/stdc++.h>

using namespace std;

int nr, N, mouse, trap, t[1000009], dp[1000009], sda[1000009], deg[1000009], node[1000009];
vector < int > v[1000009], h[1000009];

void dfs (int nod)
{
    sda[nod] = (nod == trap ? 0 : sda[t[nod]] - 1 + (int) (v[nod].size ()) - 1);
    for (auto it : v[nod])
        if (it != t[nod])
            t[it] = nod, dfs (it), deg[nod] ++;
    if (deg[nod] <= 1) dp[nod] = deg[nod];
    else
    {
        int max1 = -N, max2 = -N;
        for (auto it : v[nod])
            if (it != t[nod])
            {
                if (dp[it] > max1) max2 = max1, max1 = dp[it];
                else
                if (dp[it] > max2) max2 = dp[it];
            }
        dp[nod] = deg[nod] + max2;
    }
}

int getDp (int i, int cnt)
{
    if (cnt >= h[i].size ()) return 0;
    return h[i][cnt];
}

bool ok (int D)
{
    int minS = 0;
    for (int i=1; i<nr; i++)
    {
        int oldS = minS;
        while (minS <= i && max (0, sda[t[node[i]]] - (i - minS)) + getDp (i, minS - oldS) +
                            max (0, deg[node[i]] - (i > 1) - (minS - oldS)) + min (i, sda[t[node[i]]] + minS) > D)
            minS ++;
        if (minS > i) return 0;
    }
    return 1;
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d %d", &N, &trap, &mouse);
for (int i=1; i<N; i++)
{
    int x, y;
    scanf ("%d %d", &x, &y);
    v[x].push_back (y);
    v[y].push_back (x);
}
dfs (trap);
node[1] = mouse, nr = 1;
while (node[nr] != trap)
    node[nr + 1] = t[node[nr]], nr ++;
for (int i=1; i<=nr; i++)
{
    for (auto j : v[node[i]])
        if (j != t[node[i]] && j != node[i - 1])
            h[i].push_back (dp[j]);
    sort (h[i].begin (), h[i].end ());
    reverse (h[i].begin (), h[i].end ());
}
int p = 0, u = N, mij, ras = -1;
while (p <= u)
{
    mij = (p + u) >> 1;
    if (ok (mij)) ras = mij, u = mij - 1;
    else p = mij + 1;
}
printf ("%d\n", ras);
return 0;
}

Compilation message (stderr)

mousetrap.cpp: In function 'int getDp(int, int)':
mousetrap.cpp:31:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (cnt >= h[i].size ()) return 0;
         ~~~~^~~~~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d %d %d", &N, &trap, &mouse);
 ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:58:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &x, &y);
     ~~~~~~^~~~~~~~~~~~~~~~~

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