Submission #46594

#	Time	Username	Problem	Language	Result	Execution time	Memory
46594		alexpetrescu	Network (BOI15_net)	C++14	100 / 100	795 ms	158208 KiB

net

#include <cstdio>
#include <vector>

#define MAXN 500000

std::vector < int > g[MAXN + 1], v;
int s[MAXN + 1], cost[MAXN + 1];
bool viz[MAXN + 1], done[MAXN + 1];

void dfs(int x) {
    s[x] = g[x].size() == 1;
    viz[x] = 1;
    for (auto &y : g[x]) {
        if (viz[y] == 0) {
            dfs(y);
            s[x] += s[y];
            cost[x] = std::max(cost[x], s[y]);
        }
    }
}

void dfs2(int x) {
    if (g[x].size() == 1)
        v.push_back(x);
    done[x] = 1;
    for (auto &y : g[x])
        if (done[y] == 0)
            dfs2(y);
}

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);

        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs(1);

    int ans = n + 1, r = 0;
    for (int i = 1; i <= n; i++) {
        if (g[i].size() != 1) {
            int val = std::max(cost[i], s[1] - s[i]);
            if (val < ans)
                ans = val, r = i;
        }
    }

    printf("%d\n", (s[1] + 1) / 2);
    dfs2(r);
    int k = v.size() / 2;
    for (int i = 0; i < k; i++)
        printf("%d %d\n", v[i], v[i + k]);
    if (v.size() % 2)
        printf("%d %d\n", v.back(), v[0]);

    return 0;
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
net.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

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