oj.uz

답안 #797479

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
797479 2023-07-29T12:42:51 Z bonk Network (BOI15_net) C++14
0 / 100
 7 ms 12060 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 2;
vector<int>adj[N];
vector<pair<int, int>>t;
int timer = 0;

void dfs(int prev, int cur){
    timer++;
    bool leaf = true;
    for(auto &nxt: adj[cur]){
        if(prev == nxt) continue;
        leaf = false;
        dfs(cur, nxt);
    }

    if(leaf) t.emplace_back(timer, cur);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    for(int i = 0; i < n - 1; i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    bool tmp = false;

    for(int i = 1; i <= n; i++){
        if(adj[i].size() > 1){
            dfs(-1, i);
            break;
        }
    }

    sort(t.begin(), t.end());
    cout << (t.size() + 1)/2 << '\n';
    int l = 0, r = t.size() - 1;
    while(l < r){
        cout << t[l].second << " " << t[r].second << '\n';
        l++; r--;
    }

    if(l == r){
        cout << t[l].second << " " << t.back().second << '\n';
    }

    return 0;
}

Compilation message

net.cpp: In function 'int main()':
net.cpp:31:10: warning: unused variable 'tmp' [-Wunused-variable]
   31 |     bool tmp = false;
      |          ^~~

Subtask #1
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12060 KB Output is correct
2 Incorrect 6 ms 12044 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12060 KB Output is correct
2 Incorrect 6 ms 12044 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12060 KB Output is correct
2 Incorrect 6 ms 12044 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -