QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#388153 | #8575. Three Person Tree Game | BUET_POTATOES# | WA | 13ms | 3872kb | C++20 | 1.8kb | 2024-04-13 13:11:22 | 2024-04-13 13:11:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int dis[N];
vector<int> adj[N];
int par[N];
void dfs(int ind, int p, int d = 0){
par[ind] = p;
dis[ind] = d;
for(auto x : adj[ind]){
if(x == p)continue;
dfs(x, ind, d + 1);
}
}
int lca(int a, int b){
while(a != b){
if(dis[a] > dis[b])a = par[a];
else b = par[b];
}
return a;
}
void testcase(int cs){
int n;
cin >> n;
for(int i = 1; i <= n; ++i)adj[i].clear();
int a, b, c;
cin >> a >> b >> c;
for(int i = 1; i < n; i++){
int x, y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
for(auto x : adj[a]){
if(x == c){
cout << "A\n";
return;
}
}
dfs(a, -1);
int l = lca(b, c);
dfs(l, -1);
vector<pair<int, int>> v;
v.emplace_back(dis[a], 0);
v.emplace_back(dis[b], 1);
v.emplace_back(dis[c], 2);
sort(v.begin(), v.end());
if(v.back().first == v[0].first){
cout << "DRAW\n";
return;
}
if(dis[a] == dis[c] + 1 && dis[b] == dis[c] + 1){
cout << "DRAW\n";
return;
}
if(dis[a] == dis[b] + 1 && dis[a] == dis[c] + 1){
cout << "DRAW\n";
return;
}
string s = "ABC";
if(v[0].first == v[1].first){
if((v[0].second + 1) % 3 == v[1].second){
cout << s[v[1].second] << "\n";
}else{
cout << s[v[0].second] << "\n";
}
return;
}
cout << s[v[0].second] << "\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int T = 1;
cin >> T;
for(int cs = 1; cs <= T; ++cs){
testcase(cs);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3868kb
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: 13ms
memory: 3872kb
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 A B A A A B B B C A A A B B DRAW C DRAW A A A A A B B A C DRAW A B A B DRAW A C DRAW A B C DRAW DRAW A A A DRAW DRAW B B B A DRAW B B A A DRAW B A A B DRAW A B C C DRAW A B A A A B B B A A B B A C DRAW B A B A A A C A A DRAW A A C A DRAW C A B A...
result:
wrong answer 83rd lines differ - expected: 'A', found: 'C'