답안 #54228 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54228	2018-07-02T21:09:27 Z	SpaimaCarpatilor	Mousetrap (CEOI17_mousetrap)	C++17	100 / 100	1212 ms	250968 KB

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

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

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	47352 KB	Output is correct
2	Correct	41 ms	47396 KB	Output is correct
3	Correct	40 ms	47580 KB	Output is correct
4	Correct	39 ms	47580 KB	Output is correct
5	Correct	41 ms	47604 KB	Output is correct
6	Correct	40 ms	47604 KB	Output is correct
7	Correct	42 ms	47628 KB	Output is correct
8	Correct	41 ms	47632 KB	Output is correct
9	Correct	41 ms	47632 KB	Output is correct
10	Correct	40 ms	47708 KB	Output is correct

Subtask #2
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	495 ms	92756 KB	Output is correct
2	Correct	425 ms	92756 KB	Output is correct
3	Correct	1063 ms	95852 KB	Output is correct
4	Correct	580 ms	95852 KB	Output is correct
5	Correct	1018 ms	95852 KB	Output is correct
6	Correct	1212 ms	95852 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	47352 KB	Output is correct
2	Correct	41 ms	47396 KB	Output is correct
3	Correct	40 ms	47580 KB	Output is correct
4	Correct	39 ms	47580 KB	Output is correct
5	Correct	41 ms	47604 KB	Output is correct
6	Correct	40 ms	47604 KB	Output is correct
7	Correct	42 ms	47628 KB	Output is correct
8	Correct	41 ms	47632 KB	Output is correct
9	Correct	41 ms	47632 KB	Output is correct
10	Correct	40 ms	47708 KB	Output is correct
11	Correct	40 ms	95852 KB	Output is correct
12	Correct	41 ms	95852 KB	Output is correct
13	Correct	42 ms	95852 KB	Output is correct
14	Correct	42 ms	95852 KB	Output is correct
15	Correct	42 ms	95852 KB	Output is correct
16	Correct	40 ms	95852 KB	Output is correct
17	Correct	41 ms	95852 KB	Output is correct
18	Correct	41 ms	95852 KB	Output is correct
19	Correct	40 ms	95852 KB	Output is correct
20	Correct	40 ms	95852 KB	Output is correct
21	Correct	40 ms	95852 KB	Output is correct
22	Correct	40 ms	95852 KB	Output is correct

Subtask #4
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	47352 KB	Output is correct
2	Correct	41 ms	47396 KB	Output is correct
3	Correct	40 ms	47580 KB	Output is correct
4	Correct	39 ms	47580 KB	Output is correct
5	Correct	41 ms	47604 KB	Output is correct
6	Correct	40 ms	47604 KB	Output is correct
7	Correct	42 ms	47628 KB	Output is correct
8	Correct	41 ms	47632 KB	Output is correct
9	Correct	41 ms	47632 KB	Output is correct
10	Correct	40 ms	47708 KB	Output is correct
11	Correct	495 ms	92756 KB	Output is correct
12	Correct	425 ms	92756 KB	Output is correct
13	Correct	1063 ms	95852 KB	Output is correct
14	Correct	580 ms	95852 KB	Output is correct
15	Correct	1018 ms	95852 KB	Output is correct
16	Correct	1212 ms	95852 KB	Output is correct
17	Correct	40 ms	95852 KB	Output is correct
18	Correct	41 ms	95852 KB	Output is correct
19	Correct	42 ms	95852 KB	Output is correct
20	Correct	42 ms	95852 KB	Output is correct
21	Correct	42 ms	95852 KB	Output is correct
22	Correct	40 ms	95852 KB	Output is correct
23	Correct	41 ms	95852 KB	Output is correct
24	Correct	41 ms	95852 KB	Output is correct
25	Correct	40 ms	95852 KB	Output is correct
26	Correct	40 ms	95852 KB	Output is correct
27	Correct	40 ms	95852 KB	Output is correct
28	Correct	40 ms	95852 KB	Output is correct
29	Correct	40 ms	95852 KB	Output is correct
30	Correct	468 ms	106336 KB	Output is correct
31	Correct	485 ms	119616 KB	Output is correct
32	Correct	642 ms	201680 KB	Output is correct
33	Correct	493 ms	211124 KB	Output is correct
34	Correct	1135 ms	211124 KB	Output is correct
35	Correct	1088 ms	211124 KB	Output is correct
36	Correct	1165 ms	211124 KB	Output is correct
37	Correct	1118 ms	212236 KB	Output is correct
38	Correct	1016 ms	224156 KB	Output is correct
39	Correct	911 ms	237476 KB	Output is correct
40	Correct	991 ms	250968 KB	Output is correct

답안 #54228

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 25.0 / 25.0

Subtask #3 20.0 / 20.0

Subtask #4 35.0 / 35.0

Subtask #1
20.0 / 20.0

Subtask #2
25.0 / 25.0

Subtask #3
20.0 / 20.0

Subtask #4
35.0 / 35.0