QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#379871 | #8575. Three Person Tree Game | ucup-team3113# | WA | 19ms | 3636kb | C++20 | 1.5kb | 2024-04-06 19:38:18 | 2024-04-06 19:38:19 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
#define int int64_t
#define pii pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(),(x).end()
#define lb lower_bound
#define ub upper_bound
using namespace std;
const int inf = 1e18;
void p(auto A){
for(auto e : A)cout << e << ' ';
cout << '\n';
}
void solve(){
int n; cin >> n;
int sa, sb, sc; cin >> sa >> sb >> sc;
sa--; sb--; sc--;
vector<vector<int>>g(n);
for(int i = 0; i< n-1; i++){
int c, d; cin >> c >> d;
c--; d--;
g[c].pb(d);
g[d].pb(c);
}
int rt = -1;
auto dfs1 = [&](auto&& self, int u, int p)->int{
int ret = 0;
for(auto v : g[u])if(v!=p)ret+=self(self, v, u);
if(u == sb || u == sc)ret++;
if(rt == -1 && ret == 2)rt = u;
return ret;
};
dfs1(dfs1, sa, sa);
assert(rt != -1);
vector<int>dis(n);
auto dfs2 = [&](auto&& self, int u, int p)->void{
for(auto v : g[u])if(v!=p){
dis[v] = dis[u]+1;
self(self, v, u);
}
};
dfs2(dfs2, rt, rt);
if(dis[sa] < dis[sb] && dis[sa] <= dis[sc]+1){
cout << "A\n";
return;
}
if(dis[sb] < dis[sc] && dis[sb] <= dis[sa]){
cout << "B\n";
return;
}
if(dis[sc]+1 < dis[sa] && dis[sc] <= dis[sb]){
cout << "C\n";
return;
}
cout << "DRAW\n";
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
cin >> t;
while(t--)solve();
}
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3620kb
input:
2 3 1 2 3 2 1 3 1 4 1 2 3 1 4 2 4 3 4
output:
A DRAW
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 19ms
memory: 3636kb
input:
10000 20 2 12 1 16 15 3 2 16 17 14 13 11 12 9 8 10 9 18 17 6 5 18 19 13 12 5 4 7 6 20 19 14 15 3 4 11 10 1 2 8 7 20 12 13 1 18 13 12 11 19 15 17 16 10 14 4 2 15 11 6 5 3 2 4 13 20 8 11 9 3 7 14 16 5 8 5 4 9 6 10 3 1 2 17 2 17 15 9 10 5 4 9 8 2 11 6 7 8 7 13 4 2 3 6 15 5 6 17 8 2 1 3 4 16 7 14 5 3 12...
output:
A B C B DRAW C A A A DRAW C B B B DRAW A DRAW A C DRAW DRAW B A A A B B B C A A A B B DRAW C DRAW A A DRAW A A B B DRAW C DRAW A B DRAW B DRAW A C DRAW DRAW B C DRAW DRAW A A DRAW DRAW DRAW B B B A DRAW B B A A DRAW B A A B DRAW A B A C DRAW A B A A DRAW B B B A A B B A C DRAW B A B DRAW A A C A A D...
result:
wrong answer 21st lines differ - expected: 'A', found: 'DRAW'