Submission #79564

#	Time	Username	Problem	Language	Result	Execution time	Memory
79564		Flying_dragon_02	Network (BOI15_net)	C++14	100 / 100	665 ms	52028 KiB

net

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int N = 5e5 + 5;

int n, dp[N];
bool vis[N];
vector<int> graph[N];
vector<int> ans;

void dfs(int u, int p) {
    vis[u] = 1;
    int cnt = 0;
    for(int i = 0; i < graph[u].size(); i++) {
        int v = graph[u][i];
        if(!vis[v] && v != p) {
            dfs(v, u);
            cnt++;
        }
    }
    if(!cnt)
        ans.pb(u);
}

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].pb(v);
        graph[v].pb(u);
    }
    int cen;
    for(int i = 1; i <= n; i++) {
        if(graph[i].size() > 1)
            cen = i;
    }
    dfs(cen, cen);
    if(ans.size() % 2 == 0) {
        cout << ans.size() / 2 << "\n";
        for(int i = 0; i < ans.size() / 2; i++) {
            cout << ans[i] << " " << ans[i + ans.size() / 2] << "\n";
        }
    }
    else {
        cout << ans.size() / 2 + 1 << "\n";
        cout << ans[ans.size() / 2] << " " << cen << "\n";
        for(int i = 0; i < ans.size() / 2; i++) {
            cout << ans[i] << " " << ans[i + ans.size() / 2 + 1] << "\n";
        }
    }
}

Compilation message (stderr)

net.cpp: In function 'void dfs(int, int)':
net.cpp:22:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < graph[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~
net.cpp: In function 'int main()':
net.cpp:50:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < ans.size() / 2; i++) {
                        ~~^~~~~~~~~~~~~~~~
net.cpp:57:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < ans.size() / 2; i++) {
                        ~~^~~~~~~~~~~~~~~~
net.cpp:56:54: warning: 'cen' may be used uninitialized in this function [-Wmaybe-uninitialized]
         cout << ans[ans.size() / 2] << " " << cen << "\n";
                                                      ^~~~

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