QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#756063#8575. Three Person Tree Game_RICKK_WA 22ms3792kbC++204.1kb2024-11-16 18:54:172024-11-16 18:54:17

Judging History

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

  • [2024-11-16 18:54:17]
  • 评测
  • 测评结果:WA
  • 用时:22ms
  • 内存:3792kb
  • [2024-11-16 18:54:17]
  • 提交

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 && 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: 3792kb

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: 22ms
memory: 3556kb

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
DRAW
DRAW
A
DRAW
A
C
DRAW
A
DRAW
A
A
A
B
B
DRAW
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
DRA...

result:

wrong answer 14th lines differ - expected: 'B', found: 'DRAW'