oj.uz

Submission #639710

# Submission time Handle Problem Language Result Execution time Memory
639710 2022-09-11T08:06:55 Z Wunka Network (BOI15_net) C++17
0 / 100
 7 ms 14036 KB 
#include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5; 
vector<vector<int>> graph(N); 
vector<bool> visited(N); 
vector<int>  degree(N); 
map<int, int> leaf; 
int k = 0, mx, x; 

void dfs(int v) {
    visited[v] = true; 
    if(degree[v] == 1) {
        leaf[k] = v; 
        k++; 
    }

    for(int next : graph[v]) {
        if(!visited[next]) {
            dfs(next); 
        }
    }
}

int main() {
    int n; 
    cin >> n; 
    
    mx = 0; 
    for(int i = 0; i < n - 1; i++) {
        int a, b; 
        cin >> a >> b; 
        a--, b--; 
        degree[a]++, degree[b]++; 
        graph[a].push_back(b);
        graph[b].push_back(a);
        if(degree[a] > mx) {
            mx = degree[a]; 
            x = a; 
        }
        if(degree[b] > mx) {
            mx = degree[b]; 
            x = b; 
        }
    }

    dfs(x); 
    cout << (k + 1) / 2 << endl; 
    /*
    if(k % 2 == 1) {
        cout << x + 1 << ' ' << leaf[k] + 1 << '\n'; 
        k--; 
    }
    */

    for(int i = 0; i < k - i - 1; i++) {
        cout << leaf[i] + 1 << ' ' << leaf[k - i - 1] + 1 << endl; 
    }

    if(k % 2 == 1) {
        cout << leaf[k / 2] + 1 << ' ' << x + 1 << endl; 
    } 
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14036 KB Output is correct
2 Incorrect 7 ms 14036 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14036 KB Output is correct
2 Incorrect 7 ms 14036 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14036 KB Output is correct
2 Incorrect 7 ms 14036 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -