QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#397031#6745. Delete the TreeVictorYuan#RE 0ms0kbC++141.8kb2024-04-23 15:48:022024-04-23 15:48:03

Judging History

你现在查看的是最新测评结果

  • [2024-04-23 15:48:03]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-04-23 15:48:02]
  • 提交

answer

#include <bits/stdc++.h> 

const int maxn = 505;

int n, cnt;
std::vector<int> e[maxn], tmp[maxn];
std::vector<std::vector<int>> ans;
int del[maxn];
std::mt19937 rnd;

int getroot() {
  std::vector<int> ret;
  for (int i = 1; i <= n; ++i) if (e[i].size() == 1) { return i; }
  if (ret.size() != 0) return ret[rnd() % ret.size()];
  for (int i = 1; i <= n; ++i) if (del[i] == 0) return i;
  assert(false);
}

void dfs(const int u, int pre = -1) {
  for (auto v : e[u]) if (v != pre) {
    dfs(v, u);
  }
  if (e[u].size() == 2) {
    int v = e[u][0];
    if (v == pre) v = e[u][1];
    if (!del[v]) {
      del[u] = 1;
      ans.back().push_back(u);
    }
  } else if (e[u].size() < 2 && pre != -1) {
    del[u] = 1;
    ans.back().push_back(u);
  } else if (e[u].size() < 2) {
    if (e[u].size() == 0 || (e[u].size() == 1 && !del[e[u][0]])) {
      del[u] = 1;
      ans.back().push_back(u);
    }
  }
}

int main() {  
  rnd.seed(time(nullptr));
  std::cin >> n;
  for (int u, v, i = 1; i < n; ++i) {
    std::cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  while (cnt != n) {
    ans.push_back(std::vector<int>());
    dfs(getroot());
    for (int i = 1; i <= n; ++i) tmp[i].clear();
    for (int u = 1; u <= n; ++u) if (!del[u]) {
      for (auto v : e[u]) if (!del[v]) {
        tmp[u].push_back(v);
      }
    } else if (del[u] == 1) {
      for (auto v : e[u]) {
        for (auto k : e[u]) if (v != k) {
          tmp[v].push_back(k);
        }
      }
      del[u] = -1;
    }
    for (int i = 1; i <= n; ++i) e[i].swap(tmp[i]);
    cnt += ans.back().size();
  }
  std::cout << ans.size();
  if(ans.size() - 10 >= 5) return -1;
  assert(ans.size() <= 10);
  for (auto &i : ans) {
    std::cout << '\n' << i.size(); for (auto j : i) std::cout << ' ' << j;
  }
  std::cout << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

5
1 2
1 3
1 4
4 5

output:

3

result: