QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#95861#6307. Chase Game 2ksunhokimWA 10ms3456kbC++201.3kb2023-04-12 08:53:112023-04-12 08:53:14

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-12 08:53:14]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:3456kb
  • [2023-04-12 08:53:11]
  • 提交

answer

#include <bits/stdc++.h>
#include <queue>
using namespace std;
using ll = long long;

void solve() {
  int n;
  cin >> n;
  vector adj(n, vector<int>());

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

  map<int,int> leafs;
  vector<int> levels(n);

  auto dfs = [&](auto self, int u, int p, int level) -> void {
    int cnt = 0;
    levels[u] = level;
    for (int v : adj[u]) {
      if (v == p) continue;
      self(self, v, u, level + 1);
      cnt++;
    }
    if (cnt == 0) {
      leafs[p]++;
    }
  };
  dfs(dfs, 0, -1, 0);
  
  priority_queue<pair<int,int>> pq;
  for (auto [u, cnt] : leafs) {
    pq.push({cnt,u });
  }
  if (pq.size() == 1) {
    auto [cnt, u] = pq.top();
    if (levels[u] <= 1) {
      cout << -1 << "\n";
      return;
    }
  }
  int ans = 0;
  while (pq.size() >= 2) {
    auto [cnt, u] = pq.top();
    pq.pop();
    auto [cnt2, v] = pq.top();
    pq.pop();
    cnt--,cnt2--;
    ans++;
    if (cnt != 0) {
      pq.push({cnt, u});
    }
    if (cnt2 != 0) {
      pq.push({cnt2, v});
    }
  }
  ans += pq.top().first;
  cout << ans << "\n";
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int t;
  cin >> t;
  while (t--){
    solve();
  }
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3420kb

input:

4
2
1 2
4
1 2
2 3
3 4
4
1 2
2 3
2 4
5
1 2
2 3
3 4
3 5

output:

-1
1
-1
2

result:

ok 4 number(s): "-1 1 -1 2"

Test #2:

score: -100
Wrong Answer
time: 10ms
memory: 3456kb

input:

10000
4
1 2
1 3
3 4
4
1 2
1 3
1 4
4
1 2
2 3
1 4
5
1 2
2 3
1 4
4 5
5
1 2
2 3
3 4
4 5
4
1 2
2 3
2 4
5
1 2
1 3
2 4
2 5
4
1 2
2 3
1 4
5
1 2
1 3
2 4
1 5
5
1 2
2 3
3 4
2 5
5
1 2
1 3
2 4
2 5
4
1 2
1 3
3 4
5
1 2
1 3
3 4
1 5
4
1 2
1 3
1 4
5
1 2
1 3
3 4
3 5
5
1 2
2 3
3 4
3 5
4
1 2
1 3
2 4
5
1 2
2 3
2 4
3 5
5
...

output:

2
-1
2
2
1
-1
2
2
2
2
2
2
2
-1
2
2
2
2
2
1
2
2
-1
2
2
2
1
-1
2
2
2
1
2
-1
2
2
2
1
2
-1
2
2
2
2
2
2
1
1
-1
2
2
1
2
2
2
2
2
2
2
-1
-1
-1
2
2
2
2
2
2
2
2
2
-1
2
2
-1
2
2
-1
2
-1
-1
2
2
2
2
2
2
2
1
1
1
2
2
2
2
-1
2
2
2
-1
2
2
2
2
-1
2
-1
2
-1
-1
2
-1
2
1
2
2
2
2
2
2
2
2
2
1
2
-1
2
1
2
1
1
2
2
2
2
2
2
-1...

result:

wrong answer 1st numbers differ - expected: '1', found: '2'