oj.uz

Submission #79562

# Submission time Handle Problem Language Result Execution time Memory
79562 2018-10-15T03:10:57 Z Flying_dragon_02 Network (BOI15_net) C++14
0 / 100
 13 ms 12300 KB 
#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 + 1] << " " << cen << "\n";
        for(int i = 0; i < ans.size() / 2; i++) {
            cout << ans[i] << " " << ans[i + ans.size() / 2 + 1] << "\n";
        }
    }
}

Compilation message

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:58: warning: 'cen' may be used uninitialized in this function [-Wmaybe-uninitialized]
         cout << ans[ans.size() / 2 + 1] << " " << cen << "\n";
                                                          ^~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12024 KB Output is correct
2 Correct 12 ms 12300 KB Output is correct
3 Correct 12 ms 12300 KB Output is correct
4 Incorrect 12 ms 12300 KB Breaking single line is causing network to disconnect.
5 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12024 KB Output is correct
2 Correct 12 ms 12300 KB Output is correct
3 Correct 12 ms 12300 KB Output is correct
4 Incorrect 12 ms 12300 KB Breaking single line is causing network to disconnect.
5 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12024 KB Output is correct
2 Correct 12 ms 12300 KB Output is correct
3 Correct 12 ms 12300 KB Output is correct
4 Incorrect 12 ms 12300 KB Breaking single line is causing network to disconnect.
5 Halted 0 ms 0 KB -