oj.uz

Submission #43046

# Submission time Handle Problem Language Result Execution time Memory
43046 2018-03-08T09:22:45 Z RayaBurong25_1 Mousetrap (CEOI17_mousetrap) C++14
45 / 100
 1490 ms 64692 KB 
#include <stdio.h>
#include <vector>
std::vector<int> AdjList[1000005];
int PhaseII[1000005];
int m, t, T;
int MT[1000005];
int between;
void findMT(int u, int pa)
{
    if (u == t)
    {
        MT[u] = t;
        return;
    }
    int i, v, s = AdjList[u].size();
    for (i = 0; i < s; i++)
    {
        v = AdjList[u][i];
        if (v != pa)
        {
            findMT(v, u);
            if (MT[v])
                MT[u] = v;
        }
    }
}
void calcPhaseII(int u, int pa)
{
    int i, v, s = AdjList[u].size();
    int S = s;
    for (i = 0; i < s; i++)
    {
        v = AdjList[u][i];
        if (v != pa && MT[v])
            S--;
    }
    if (S == 1 || S == 2)
        PhaseII[u] = 1 - (pa == T);
    else if (pa == T)
        PhaseII[u] = S - 3;
    else
        PhaseII[u] = S - 2;
    PhaseII[u] += PhaseII[pa];
    // printf("u%d PhaseII%d\n", u, PhaseII[u]);
    for (i = 0; i < s; i++)
    {
        v = AdjList[u][i];
        if (v != pa && !MT[v])
            calcPhaseII(v, u);
    }
}
int PhaseI[1000005];
int min(int a, int b)
{
    return (a < b)?a:b;
}
void calcPhaseI(int u, int pa)
{
    int i, v, s = AdjList[u].size();
    int S = s;
    for (i = 0; i < s; i++)
    {
        v = AdjList[u][i];
        if (v != pa && MT[v])
            S--;
    }
    int p = PhaseII[u], q = PhaseII[u];
    for (i = 0; i < s; i++)
    {
        v = AdjList[u][i];
        if (v != pa && !MT[v])
        {
            calcPhaseI(v, u);
            if (PhaseI[v] >= p)
            {
                q = p;
                p = PhaseI[v];
            }
            else if (PhaseI[v] >= q)
                q = PhaseI[v];
        }
    }
    if (S == 1)
        PhaseI[u] = q;
    else
        PhaseI[u] = 1 + q;
    // printf("u%d PhaseI%d\n", u, PhaseI[u]);
}
int main()
{
    int n;
    scanf("%d %d %d", &n, &t, &m);
    int i, u, v;
    for (i = 0; i < n - 1; i++)
    {
        scanf("%d %d", &u, &v);
        AdjList[u].push_back(v);
        AdjList[v].push_back(u);
    }
    findMT(m, 0);
    for (i = 1; i <= n; i++)
    {
        // printf("MT %d\n", MT[i]);
        if (MT[i] && i != m && i != t)
            between += AdjList[i].size() - 2;
    }
    int ans = 0;
    u = m;
    while (u != t)
    {
        T = MT[u];
        calcPhaseII(u, T);
        calcPhaseI(u, T);
        ans += PhaseI[u];
        u = MT[u];
        break;
        // printf("ans %d\n", ans);
    }
    // printf("ans %d between %d\n", ans, between);
    ans += between;
    printf("%d", ans);
}

Compilation message

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:92:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &t, &m);
                                  ^
mousetrap.cpp:96:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
                               ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 22 ms 24032 KB Output is correct
3 Correct 22 ms 24032 KB Output is correct
4 Correct 23 ms 24120 KB Output is correct
5 Correct 27 ms 24120 KB Output is correct
6 Correct 22 ms 24120 KB Output is correct
7 Correct 22 ms 24120 KB Output is correct
8 Correct 22 ms 24288 KB Output is correct
9 Correct 22 ms 24292 KB Output is correct
10 Correct 22 ms 24292 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 63552 KB Output is correct
2 Correct 449 ms 63552 KB Output is correct
3 Correct 1475 ms 64624 KB Output is correct
4 Correct 692 ms 64624 KB Output is correct
5 Correct 1471 ms 64692 KB Output is correct
6 Correct 1490 ms 64692 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 22 ms 24032 KB Output is correct
3 Correct 22 ms 24032 KB Output is correct
4 Correct 23 ms 24120 KB Output is correct
5 Correct 27 ms 24120 KB Output is correct
6 Correct 22 ms 24120 KB Output is correct
7 Correct 22 ms 24120 KB Output is correct
8 Correct 22 ms 24288 KB Output is correct
9 Correct 22 ms 24292 KB Output is correct
10 Correct 22 ms 24292 KB Output is correct
11 Incorrect 21 ms 64692 KB Output isn't correct
12 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 22 ms 24032 KB Output is correct
3 Correct 22 ms 24032 KB Output is correct
4 Correct 23 ms 24120 KB Output is correct
5 Correct 27 ms 24120 KB Output is correct
6 Correct 22 ms 24120 KB Output is correct
7 Correct 22 ms 24120 KB Output is correct
8 Correct 22 ms 24288 KB Output is correct
9 Correct 22 ms 24292 KB Output is correct
10 Correct 22 ms 24292 KB Output is correct
11 Correct 523 ms 63552 KB Output is correct
12 Correct 449 ms 63552 KB Output is correct
13 Correct 1475 ms 64624 KB Output is correct
14 Correct 692 ms 64624 KB Output is correct
15 Correct 1471 ms 64692 KB Output is correct
16 Correct 1490 ms 64692 KB Output is correct
17 Incorrect 21 ms 64692 KB Output isn't correct
18 Halted 0 ms 0 KB -