QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#332106#6307. Chase Game 2martinius#WA 8ms3556kbC++201.1kb2024-02-19 08:58:262024-02-19 08:58:28

Judging History

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

  • [2024-02-19 08:58:28]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:3556kb
  • [2024-02-19 08:58:26]
  • 提交

answer

#include <bits/stdc++.h>

#define forn(i,n) for(int i=0; i < n; ++i)
#define pb push_back
#define el '\n'
#define sz(v) int(v.size())

using namespace std;

typedef vector<int> vi;
const int N = 2e5 + 10;
vi g[N];

void borre(int n){
  forn(i, n) g[i].clear();
}

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  int t; cin >> t;
  while(t--){
    int n; cin >> n;
    forn(i, n-1){
      int u, v; cin >> u >> v;
      --u, --v;
      g[u].pb(v);
      g[v].pb(u);
    }

    vi cnt(n);
    forn(i, n){
      if(sz(g[i]) == 1){
        cnt[g[i][0]]++;
      }
    }

    priority_queue<int, vi, greater<int>> pq;
    forn(i, n){
      if(cnt[i]) pq.push(cnt[i]);
    }

    if(n == 2 || sz(pq) == 1){
      cout << -1 << el;
      borre(n);
      continue;
    }

    int ans = 0;
    while(sz(pq) > 1){
      ++ans;
      int c1 = pq.top(); pq.pop();
      int c2 = pq.top(); pq.pop();
      --c1, --c2;
      if(c1) pq.push(c1);
      if(c2) pq.push(c2);
    }
    if(sz(pq)) ans += pq.top();
    cout << ans << el;
    borre(n);
  }
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3520kb

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: 0
Accepted
time: 4ms
memory: 3552kb

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:

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

result:

ok 10000 numbers

Test #3:

score: -100
Wrong Answer
time: 8ms
memory: 3556kb

input:

10000
9
1 2
2 3
3 4
4 5
1 6
6 7
5 8
7 9
9
1 2
2 3
2 4
1 5
2 6
4 7
6 8
1 9
9
1 2
2 3
1 4
4 5
5 6
4 7
2 8
1 9
10
1 2
2 3
1 4
3 5
3 6
2 7
6 8
6 9
6 10
10
1 2
1 3
3 4
2 5
1 6
5 7
4 8
2 9
7 10
10
1 2
2 3
2 4
1 5
3 6
6 7
5 8
4 9
9 10
9
1 2
2 3
2 4
1 5
3 6
2 7
1 8
2 9
9
1 2
1 3
2 4
1 5
3 6
3 7
7 8
8 9
10
1...

output:

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

result:

wrong answer 4th numbers differ - expected: '3', found: '4'