QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#657572 | #6307. Chase Game 2 | Fluoresce# | WA | 23ms | 6944kb | C++20 | 1.7kb | 2024-10-19 15:00:10 | 2024-10-19 15:00:11 |
Judging History
answer
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
typedef long long ll;
typedef long double ld;
#define debug(a) cout<<a<<'\n'
#define Pll pair<ll,ll>
#define PII pair<int,int>
#define ft first
#define sd second
#define vec vector
#define pushk push_back
#define ump unordered_map
#define pl p<<1
#define pr p<<1|1
using namespace std;
const int N = 2e5 + 10, M = 1e4 + 10, mod = 1e9 + 7;
const ll inf = 1e18;
const ld eps = 1e-13;
int mov[4][2] = { {0,1},{1,0},{-1,0},{0,-1} }, dx, dy, _ = 1, __ = 1;
void bout(bool f) {
if (f)cout << "Yes\n";
else cout << "No\n";
}
ll n, m, k;
int h[N],e[N<<1],ne[N<<1],idx;
void link(int x,int y){
e[++idx]=y;
ne[idx]=h[x];
h[x]=idx;
}
map<int,int>mp;
int sum=0,cnt=0,dep;
bool vis[N];
bool dfs(int u,int dp){
vis[u]=1;
int d=0;
bool f=1;
for(int i=h[u];~i;i=ne[i]){
int v=e[i];
if(!vis[v]){
if(dfs(v,dp+1))
++d;
f=0;
}
}
vis[u]=0;
if(d){
++cnt;
++mp[d];
}
sum+=d;
dep=max(dep,dp);
return f;
}
void ini() {
}
void solve() {
cin>>n;
memset(h,-1,4*(n+3));idx=0;
mp.clear();
sum=0;cnt=0;
int x,y,rt=1;
for(int i=1;i<n;++i){
cin>>x>>y;
if(h[x])rt=x;
else if(h[y])rt=y;
link(x,y);
link(y,x);
}
dep=1;
dfs(rt,1);
if(cnt>1||dep>3)cout<<max((*mp.rbegin()).ft,(sum+1)/2)<<'\n';
else cout<<"-1\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
streambuf* cinbackup = cin.rdbuf(), * coutbackup = cout.rdbuf();
ifstream fin("in.txt");
ofstream fout("out.txt");
cin.rdbuf(fin.rdbuf());
cout.rdbuf(fout.rdbuf());
#endif
cin >> _;
__ = _;
ini();
while (_--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5704kb
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: 0ms
memory: 5788kb
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: 0
Accepted
time: 5ms
memory: 5724kb
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 3 2 2 3 2 3 2 3 2 3 2 3 3 3 2 3 2 3 2 3 3 2 2 3 3 3 3 3 3 2 3 3 3 4 3 3 3 2 3 3 3 3 3 2 3 3 3 3 3 3 2 3 2 3 2 2 3 3 4 3 4 3 3 2 2 3 2 2 2 3 3 2 3 3 2 4 3 3 3 2 3 2 2 3 3 3 3 2 3 3 2 3 3 3 3 3 2 3 2 2 3 5 3 3 2 2 3 2 3 4 2 5 3 2 3 3 2 3 2 3 3 3 3 2 2 3 3 3 2 3 3 3 3 3 3 2 3 3 2 2 4 3 3 3 3 2 3 ...
result:
ok 10000 numbers
Test #4:
score: 0
Accepted
time: 8ms
memory: 5732kb
input:
10000 9 1 2 2 3 1 4 2 5 3 6 5 7 2 8 2 9 9 1 2 2 3 1 4 2 5 5 6 5 7 1 8 7 9 9 1 2 1 3 1 4 1 5 4 6 5 7 1 8 6 9 9 1 2 1 3 3 4 2 5 2 6 6 7 6 8 6 9 10 1 2 1 3 2 4 1 5 2 6 5 7 4 8 1 9 9 10 10 1 2 1 3 3 4 4 5 5 6 2 7 7 8 7 9 1 10 10 1 2 1 3 3 4 3 5 1 6 2 7 3 8 3 9 6 10 10 1 2 2 3 1 4 1 5 3 6 2 7 6 8 4 9 5 1...
output:
3 3 3 3 3 2 4 2 2 3 3 3 3 3 3 3 3 3 2 3 3 3 2 2 2 3 3 2 3 2 3 3 3 2 3 2 3 3 3 3 4 2 2 3 2 2 3 4 3 4 3 3 3 3 3 3 3 2 3 3 2 2 3 4 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 1 2 3 2 2 3 3 2 3 3 2 2 3 2 3 2 3 3 2 2 3 3 2 3 3 3 2 3 3 2 2 3 3 3 2 3 3 5 4 3 2 3 2 3 3 3 3 2 2 3 3 3 3 3 3 2 3 2 3 3 3 4 3 2 3 2 3 3 3 2 ...
result:
ok 10000 numbers
Test #5:
score: 0
Accepted
time: 17ms
memory: 5732kb
input:
10000 20 1 2 1 3 1 4 2 5 4 6 6 7 2 8 4 9 7 10 6 11 4 12 6 13 13 14 10 15 8 16 11 17 5 18 15 19 10 20 19 1 2 1 3 2 4 3 5 4 6 1 7 1 8 2 9 4 10 10 11 8 12 2 13 4 14 1 15 4 16 4 17 14 18 3 19 20 1 2 1 3 1 4 1 5 1 6 5 7 3 8 5 9 1 10 8 11 8 12 2 13 7 14 4 15 2 16 12 17 14 18 18 19 1 20 19 1 2 1 3 3 4 2 5 ...
output:
5 6 5 5 5 4 5 6 3 6 5 4 5 6 5 6 5 5 5 5 5 4 5 5 5 6 6 5 6 4 5 5 6 4 5 5 4 5 3 6 5 5 6 5 5 4 5 3 6 6 5 5 6 4 6 5 5 5 6 5 5 5 4 6 4 5 5 5 4 5 5 5 6 7 5 5 6 6 4 6 5 5 5 5 6 6 5 6 6 6 4 5 6 4 5 4 4 5 5 6 5 5 5 7 5 5 5 5 4 4 6 4 6 4 5 4 4 6 4 5 5 5 4 5 5 5 6 5 5 6 5 5 3 4 6 4 4 5 5 5 4 4 6 5 5 5 5 6 5 6 ...
result:
ok 10000 numbers
Test #6:
score: 0
Accepted
time: 12ms
memory: 5716kb
input:
4000 45 1 2 2 3 2 4 4 5 2 6 2 7 7 8 8 9 1 10 1 11 3 12 11 13 8 14 13 15 8 16 16 17 12 18 11 19 6 20 3 21 6 22 15 23 13 24 2 25 22 26 8 27 20 28 1 29 22 30 9 31 12 32 7 33 31 34 31 35 25 36 19 37 34 38 4 39 14 40 40 41 3 42 42 43 26 44 21 45 46 1 2 2 3 2 4 3 5 4 6 2 7 6 8 1 9 1 10 9 11 4 12 8 13 6 14...
output:
11 11 12 14 10 11 14 11 14 12 11 12 12 11 13 12 12 13 12 13 10 10 13 12 11 11 12 11 12 12 11 12 13 10 14 12 11 9 11 12 12 11 13 12 14 13 10 9 12 13 12 12 12 14 12 11 13 11 13 13 14 11 13 13 13 11 11 13 11 13 13 11 11 12 12 11 11 11 13 12 13 11 13 12 12 13 13 12 13 14 11 12 11 12 11 12 12 13 14 12 12...
result:
ok 4000 numbers
Test #7:
score: 0
Accepted
time: 16ms
memory: 5780kb
input:
2000 94 1 2 2 3 3 4 4 5 1 6 3 7 5 8 4 9 3 10 7 11 8 12 12 13 4 14 12 15 12 16 5 17 13 18 6 19 16 20 14 21 17 22 7 23 10 24 1 25 22 26 18 27 23 28 19 29 17 30 13 31 11 32 8 33 3 34 21 35 23 36 35 37 28 38 6 39 15 40 28 41 26 42 36 43 1 44 37 45 1 46 30 47 7 48 37 49 3 50 23 51 47 52 33 53 1 54 34 55 ...
output:
25 23 22 23 25 23 24 25 21 21 24 24 23 21 25 25 25 23 25 24 23 22 26 26 23 24 25 26 24 23 22 25 25 24 23 22 24 22 24 23 24 26 25 22 22 22 25 21 25 24 26 26 25 24 25 24 24 25 23 24 23 24 21 23 24 25 22 25 24 25 22 25 22 23 24 26 25 27 23 24 25 25 23 23 24 23 23 25 25 27 22 21 23 28 27 23 25 26 23 23 ...
result:
ok 2000 numbers
Test #8:
score: 0
Accepted
time: 17ms
memory: 5788kb
input:
200 959 1 2 1 3 2 4 2 5 3 6 1 7 5 8 7 9 1 10 2 11 2 12 6 13 9 14 14 15 3 16 6 17 12 18 5 19 7 20 12 21 18 22 1 23 8 24 11 25 2 26 19 27 4 28 21 29 15 30 22 31 21 32 32 33 15 34 22 35 11 36 22 37 34 38 18 39 7 40 13 41 29 42 40 43 34 44 28 45 37 46 10 47 8 48 12 49 2 50 17 51 39 52 35 53 16 54 31 55 ...
output:
236 231 238 231 227 235 241 230 238 230 236 237 224 237 241 235 244 242 245 243 234 236 239 231 228 227 228 238 243 234 238 255 253 230 239 254 226 233 230 242 235 240 235 242 229 249 246 249 242 243 234 237 235 227 249 240 244 233 234 244 241 233 234 225 237 242 239 242 232 248 233 234 220 222 227 ...
result:
ok 200 numbers
Test #9:
score: 0
Accepted
time: 19ms
memory: 5900kb
input:
20 9597 1 2 1 3 1 4 4 5 3 6 2 7 2 8 2 9 5 10 7 11 2 12 9 13 2 14 1 15 5 16 11 17 16 18 2 19 11 20 9 21 12 22 16 23 10 24 21 25 12 26 9 27 6 28 1 29 13 30 15 31 18 32 6 33 26 34 21 35 16 36 19 37 30 38 36 39 30 40 27 41 14 42 40 43 32 44 2 45 34 46 4 47 26 48 32 49 24 50 17 51 27 52 36 53 44 54 7 55 ...
output:
2403 2490 2391 2263 2356 2482 2384 2469 2386 2265 2283 2342 2381 2382 2261 2353 2287 2499 2458 2426
result:
ok 20 numbers
Test #10:
score: 0
Accepted
time: 23ms
memory: 6944kb
input:
2 92316 1 2 2 3 1 4 3 5 2 6 1 7 6 8 8 9 4 10 5 11 4 12 8 13 5 14 7 15 14 16 15 17 4 18 12 19 3 20 1 21 4 22 8 23 16 24 20 25 15 26 15 27 7 28 7 29 15 30 27 31 18 32 14 33 28 34 22 35 11 36 16 37 30 38 30 39 5 40 32 41 16 42 12 43 26 44 16 45 38 46 34 47 35 48 41 49 22 50 18 51 7 52 5 53 1 54 37 55 1...
output:
22980 24011
result:
ok 2 number(s): "22980 24011"
Test #11:
score: -100
Wrong Answer
time: 5ms
memory: 5724kb
input:
10000 9 9 2 5 7 8 9 9 4 3 5 3 6 9 5 1 9 9 4 2 9 4 4 8 1 4 9 7 4 6 5 3 5 4 9 4 1 9 6 7 4 4 2 7 5 2 3 6 2 3 8 9 7 9 6 8 5 2 9 4 1 3 6 5 4 6 6 3 9 6 3 3 5 3 2 4 1 1 8 3 1 9 4 3 7 10 6 4 1 3 1 6 7 9 6 9 4 8 4 10 2 9 3 5 9 8 2 8 9 8 3 9 7 5 9 1 3 3 6 4 9 10 4 6 3 5 7 6 3 2 6 10 6 8 9 6 6 2 6 1 9 8 4 7 1 ...
output:
3 4 2 2 4 3 3 6 3 4 -1 4 5 4 2 4 2 5 4 4 3 3 1 5 5 4 3 5 6 5 -1 3 5 -1 -1 4 -1 4 3 3 3 2 -1 -1 5 3 -1 3 5 5 -1 5 4 4 -1 3 2 3 3 2 2 5 -1 3 -1 4 3 -1 4 4 4 3 3 4 4 3 2 -1 -1 3 2 5 4 2 -1 4 2 3 -1 3 2 -1 6 4 2 5 3 4 4 2 3 2 2 -1 -1 5 4 3 3 -1 -1 -1 2 3 4 5 -1 5 3 -1 5 -1 2 3 6 6 4 2 4 2 6 -1 5 5 3 6 2...
result:
wrong answer 1st numbers differ - expected: '4', found: '3'