Submission #44645

#	Time	Username	Problem	Language	Result	Execution time	Memory
44645		RayaBurong25_1	Network (BOI15_net)	C++17	18 / 100	2053 ms	12928 KiB

net

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cassert>
std::vector<int> AdjList[500005];
std::vector<int> Leaf;
int Root;
int H[500005];
int Pa[500005][20];
void dfs(int u, int pa, int h)
{
    H[u] = h;
    Pa[u][0] = pa;
    if (pa == 0)
        Root = u;
    int i, v, s = AdjList[u].size();
    for (i = 0; i < s; i++)
    {
        v = AdjList[u][i];
        if (v != pa)
        {
            dfs(v, u, h + 1);
        }
    }
    if (s == 1)
        Leaf.push_back(u);
}
int cnt;
int M[500005];
int lca(int u, int v)
{
    int i;
    if (H[v] > H[u])
        return lca(v, u);
    if (H[u] > H[v])
    {
        for (i = 19; i >= 0; i--)
        {
            if (H[Pa[u][i]] > H[v])
                u = Pa[u][i];
        }
        u = Pa[u][0];
    }
    if (u == v)
        return u;
    for (i = 19; i >= 0; i--)
    {
        if (Pa[u][i] != Pa[v][i])
        {
            u = Pa[u][i];
            v = Pa[v][i];
        }
    }
    u = Pa[u][0];
    return u;
}
void mark(int u, int v)
{
    // printf("mark u%d v%d lca%d\n", u, v, lca(u, v));
    M[u]++;
    M[v]++;
    M[lca(u, v)] -= 2;
}
void dfscheck(int u, int pa)
{
    int i, v, s = AdjList[u].size();
    for (i = 0; i < s; i++)
    {
        v = AdjList[u][i];
        if (v != pa)
        {
            dfscheck(v, u);
            M[u] += M[v];
        }
    }
    // printf("M[%d] = %d\n", u, M[u]);
    assert(M[u] >= 0);
    if (M[u] == 0 && pa != 0) cnt++;
}
int N;
int check()
{
    int i, j;
    for (i = 1; i <= N; i++)
        M[i] = 0;
    cnt = 0;
    for (i = 0, j = Leaf.size() - 1; i < j; i++, j--)
        mark(Leaf[i], Leaf[j]);
    if (i == j)
        mark(Leaf[i], Root);
    if (AdjList[1].size() > 1)
        dfscheck(1, 0);
    else
        dfscheck(AdjList[1][0], 0);
    return (cnt == 0);
}
int main()
{
    scanf("%d", &N);
    int i, j, u, v;
    for (i = 0; i < N - 1; i++)
    {
        scanf("%d %d", &u, &v);
        AdjList[u].push_back(v);
        AdjList[v].push_back(u);
    }
    if (AdjList[1].size() > 1)
        dfs(1, 0, 0);
    else
        dfs(AdjList[1][0], 0, 0);
    for (j = 1; j < 20; j++)
    {
        for (i = 1; i <= N; i++)
        {
            Pa[i][j] = Pa[Pa[i][j - 1]][j - 1];
        }
    }
    printf("%d\n", (Leaf.size() + 1)/2);
    // if (check())
    // {
    //     for (i = 0, j = Leaf.size() - 1; i < j; i++, j--)
    //         printf("%d %d\n", Leaf[i], Leaf[j]);
    //     if (i == j)
    //         printf("%d %d\n", Leaf[i], Root);
    // }
    // else
    // {
    //     Leaf.push_back(Leaf[0]);
    //     Leaf.erase(Leaf.begin());
    //     if (!check())
    //         assert(1 == 0);
    //     for (i = 0, j = Leaf.size() - 1; i < j; i++, j--)
    //         printf("%d %d\n", Leaf[i], Leaf[j]);
    //     if (i == j)
    //         printf("%d %d\n", Leaf[i], Root);
    // }
    int cnt = 0;
    while (!check())
    {
        // Leaf.push_back(Leaf[0]);
        // Leaf.erase(Leaf.begin());
        std::next_permutation(Leaf.begin(), Leaf.end());
    }
    if (cnt == Leaf.size())
        assert(1 == 0);
    for (i = 0, j = Leaf.size() - 1; i < j; i++, j--)
        printf("%d %d\n", Leaf[i], Leaf[j]);
    if (i == j)
        printf("%d %d\n", Leaf[i], Root);
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:118:39: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n", (Leaf.size() + 1)/2);
                    ~~~~~~~~~~~~~~~~~~~^
net.cpp:144:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (cnt == Leaf.size())
         ~~~~^~~~~~~~~~~~~~
net.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
net.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 0 / 45
• Subtask 3: 0 / 37