oj.uz

답안 #732073

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
732073 2023-04-28T10:54:57 Z ollel Network (BOI15_net) C++17
18 / 100
 1 ms 320 KB 

#include <bits/stdc++.h>
using namespace std;
#include <iostream>

typedef vector<int> vi;
typedef vector<vi> vvi;

#define pb push_back
#define rep(i,a,b) for(int i = a; i < b; i++)

int n;
vvi g;
vi leaf;
int total_leafs;
vvi groups;

void dfs(int x, int p) {
  for (auto y : g[x]) {
    if (y == p) continue;
    dfs(y, x);
    leaf[x] += leaf[y];
  }
}

bool test(int r) {
  if (g[r].size() == 1) return false;
  for (auto y : g[r]) if (leaf[y] <= leaf[r]) if (leaf[y] > total_leafs / 2) return false;
  if (total_leafs - leaf[r] > total_leafs / 2) return false;
  return true;
}

void dfs2(int x, int p, vi & group) {
  for (auto y : g[x]) {
    if (y == p) continue;
    dfs2(y, x, group);
  }
  if (g[x].size() == 1) group.pb(x);
}

int main() {
  cin >> n;

  if (n == 2) {
    cout << 1 << "\n" << 1 << " " << 2 << endl;
    exit(0);
  }

  g.resize(n);
  rep(i,0,n-1) {
    int a, b;
    cin >> a >> b;
    a--;b--;
    g[a].pb(b);
    g[b].pb(a);
  }

  leaf.assign(n, 0);
  rep(i,0,n) if (g[i].size() == 1) leaf[i] = 1;

  int root = 0;
  while (leaf[root] > 0) root++;
  dfs(root, -1);
  total_leafs = leaf[root];

  while (!test(root)) root++;

  for (auto y : g[root]) {
    vi group;
    dfs2(y, root, group);
    groups.pb(group);
  }


  priority_queue<pair<int,int>> pq;
  int I = 0;
  for (auto & gr : groups) {
    pq.push({gr.size(), I});
    I++;
  }
  vector<pair<int,int>> ans;

  while (true) {
    pair<int,int> a = pq.top(); pq.pop();
    pair<int,int> b = pq.top(); pq.pop();

    if (a.first == 0) break;
    if (b.first == 0) {
      ans.pb({groups[a.second][0], root});
      break;
    }
    ans.pb({groups[a.second][a.first-1], groups[b.second][b.first-1]});
    pq.push({a.first-1, a.second});
    pq.push({b.first-1, b.second});
  }

  cout << ans.size() << endl;
  for (auto [a, b] : ans) {
    cout << a + 1 << " " << b + 1 << endl;
  }

}

Subtask #1
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 236 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 296 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 304 KB Output is correct

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 236 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 296 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 304 KB Output is correct
21 Runtime error 1 ms 304 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 236 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 296 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 304 KB Output is correct
21 Runtime error 1 ms 304 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -