QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#95861 | #6307. Chase Game 2 | ksunhokim | WA | 10ms | 3456kb | C++20 | 1.3kb | 2023-04-12 08:53:11 | 2023-04-12 08:53:14 |
Judging History
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'