QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#756155 | #8575. Three Person Tree Game | _RICKK_ | WA | 19ms | 3672kb | C++20 | 4.1kb | 2024-11-16 19:11:19 | 2024-11-16 19:11:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvll;
typedef vector<long long> vll;
typedef vector<pair<ll,ll>> vpll;
typedef priority_queue<ll, vector<ll>, greater<ll> > pqrll;
#define fr(i,n,a) for(long long i=a; i<n; i++)
#define ufr(i,n,a) for(long long i=n-1; i>=a; i--)
#define vout(v) for(auto &e:v){cout<<e<<" ";} cout<<"\n";
#define mout(mp) for(auto &e:mp){cout<<e.first<<"------>"<<e.second<<"\n";} cout<<endl;
#define mvout(mp) for(auto &e:mp){cout<<e.first<<"----->\n"; for(long long i =0 ; i<(e.second).size();i++){cout<<(e.second)[i]<<" ";} cout<<"\n";} cout<<"\n";
#define Sort(a) sort(a.begin(),a.end())
#define all(a) a.begin(),a.end()
#define Sorta(a,n) sort(a,a+n)
#define pb push_back
#define F first
#define S second
const ll M = 1000000000+7;
struct LCA {
vector<ll> height, euler, first, segtree;
vector<bool> visited;
ll n;
LCA(vector<vector<ll>> &adj, ll root = 0) {
n = adj.size();
height.resize(n);
first.resize(n);
euler.reserve(n * 2);
visited.assign(n, false);
dfs(adj, root);
ll m = euler.size();
segtree.resize(m * 4);
build(1, 0, m - 1);
}
void dfs(vector<vector<ll>> &adj, ll node, ll h = 0) {
visited[node] = true;
height[node] = h;
first[node] = euler.size();
euler.push_back(node);
for (auto to : adj[node]) {
if (!visited[to]) {
dfs(adj, to, h + 1);
euler.push_back(node);
}
}
}
void build(ll node, ll b, ll e) {
if (b == e) {
segtree[node] = euler[b];
} else {
ll mid = (b + e) / 2;
build(node << 1, b, mid);
build(node << 1 | 1, mid + 1, e);
ll l = segtree[node << 1], r = segtree[node << 1 | 1];
segtree[node] = (height[l] < height[r]) ? l : r;
}
}
ll query(ll node, ll b, ll e, ll L, ll R) {
if (b > R || e < L)
return -1;
if (b >= L && e <= R)
return segtree[node];
ll mid = (b + e) >> 1;
ll left = query(node << 1, b, mid, L, R);
ll right = query(node << 1 | 1, mid + 1, e, L, R);
if (left == -1) return right;
if (right == -1) return left;
return height[left] < height[right] ? left : right;
}
ll lca(ll u, ll v) {
ll left = first[u], right = first[v];
if (left > right)
swap(left, right);
return query(1, 0, euler.size() - 1, left, right);
}
};
ll dist[200005];
void dfss(ll v,vvll&g,ll p,ll dis){
dist[v]=dis;
for(auto &e:g[v]){
if(e==p){
continue;
}
dfss(e,g,v,dis+1);
}
}
void solve(){
ll n;
cin>>n;
ll a[3];
fr(i,3,0){
cin>>a[i];
}
vvll v(n+1,vll());
fr(i,n-1,0){
ll s1,s2;
cin>>s1>>s2;
v[s2].pb(s1);
v[s1].pb(s2);
}
fr(i,n+4,0){
dist[i]=0;
}
LCA lcaSolver(v,a[0]);
ll lca = lcaSolver.lca(a[1],a[2]);
dfss(a[0],v,-1,0);
// cout<<lca<<"\n";
ll dist1=abs(dist[a[0]]-dist[lca]);
ll dist2=abs(dist[a[1]]-dist[lca]);
ll dist3=abs(dist[a[2]]-dist[lca]);
ll mn=min(dist1,min(dist2,dist3));
if((dist1-dist2==1 && dist2== dist3 && mn!=0) || (dist1-dist2==0 && dist1-dist3<=1 && dist1-dist3>=0 && mn!=0) ){
cout<<"DRAW\n";
}else if(dist1==mn && dist2>mn){
cout<<"A\n";
}else if(dist2==mn && dist3>mn){
cout<<"B\n";
}else{
if(lca==a[2] && dist1==1){
cout<<"A\n";
}else{
cout<<"C\n";
}
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t=1;
cin>>t;
ll counter =1;
while(t--){
//cout<<"Case #"<<counter<<": ";
solve();
counter++;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
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: 3672kb
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'