oj.uz

답안 #656039

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
656039 2022-11-06T08:59:37 Z mhn2 Network (BOI15_net) C++17
0 / 100
 19 ms 35540 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

const int N = 5e5+5;
vector<int> adj[N], lo[N], ch[N];
vector<pii> edge;

void dfs1(int v, int p) {
    for (int u : adj[v])
        if (u != p) {
            ch[v].push_back(u);
            dfs1(u, v);
        }
}

void dfs2(int v) {
    if (ch[v].size() == 0) {
        lo[v].push_back(v);
        return;
    }

    vector<int> a, b;
    for (int u : ch[v]) {
        dfs2(u);
        if (lo[u].size() == 2) {
            a.push_back(lo[u][0]);
            a.push_back(lo[u][1]);
        }
        else
            b.push_back(lo[u][0]);
    }
    for (int x : b)
        a.push_back(x);
    
    lo[v].push_back(a[0]);
    for (int i = 1; i < a.size()-1; i += 2)
        edge.push_back({a[i], a[i+1]});
    if (!(a.size() & 1))
        lo[v].push_back(a.back());
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, r;
    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);
    }
    for (r = 1; r <= n; r++)
        if (adj[r].size() == 1)
            break;

    dfs1(r, r);
    dfs2(r);

    for (int x : lo[1])
        edge.push_back({1, x});
    
    cout << edge.size() << endl;
    for (pii x : edge)
        cout << x.F << ' ' << x.S << endl;
}

Compilation message

net.cpp: In function 'void dfs2(int)':
net.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 1; i < a.size()-1; i += 2)
      |                     ~~^~~~~~~~~~~~

Subtask #1
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 35540 KB Breaking single line is causing network to disconnect.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 35540 KB Breaking single line is causing network to disconnect.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 35540 KB Breaking single line is causing network to disconnect.
2 Halted 0 ms 0 KB -