/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 3ms 6.527 MiB
#2 Accepted 3ms 6.543 MiB
#3 Accepted 3ms 6.512 MiB
#4 Accepted 4ms 6.527 MiB
#5 Accepted 3ms 6.527 MiB
#6 Accepted 475ms 29.523 MiB
#7 Accepted 449ms 29.355 MiB
#8 Accepted 447ms 29.367 MiB
#9 Accepted 456ms 29.508 MiB
#10 Accepted 459ms 29.418 MiB
#11 Accepted 448ms 29.477 MiB
#12 Accepted 451ms 29.402 MiB
#13 Accepted 450ms 29.426 MiB
#14 Accepted 470ms 29.461 MiB
#15 Accepted 467ms 29.477 MiB
#16 Accepted 440ms 29.531 MiB
#17 Accepted 444ms 29.301 MiB
#18 Accepted 424ms 29.609 MiB
#19 Accepted 451ms 29.453 MiB
#20 Accepted 449ms 29.309 MiB
#21 Accepted 445ms 29.344 MiB
#22 Accepted 615ms 37.402 MiB
#23 Accepted 618ms 37.379 MiB
#24 Accepted 649ms 37.262 MiB
#25 Accepted 624ms 37.176 MiB
#26 Accepted 633ms 37.32 MiB
#27 Accepted 640ms 37.363 MiB
#28 Accepted 726ms 34.785 MiB
#29 Accepted 706ms 34.84 MiB
#30 Accepted 733ms 34.707 MiB
#31 Accepted 521ms 44.934 MiB
#32 Accepted 496ms 44.996 MiB
#33 Accepted 650ms 30.156 MiB
#34 Accepted 617ms 29.832 MiB
#35 Accepted 631ms 30.043 MiB

Code

/*
 *   Copyright (c) 2024 Emon Thakur
 *   All rights reserved.
 */
#include<bits/stdc++.h>
using namespace std;
int a[200005],vulcnt[200005],depth[200005];
vector<int> g[200005];

void precal(int node,int par,int dep)
{
    if(a[node]) vulcnt[node]=1;
    depth[node] = dep;
    for(auto e:g[node])
    {
        if(e==par) continue;
        precal(e,node,dep+1);
    }
    for(auto e:g[node])
    {
        if(e==par) continue;
        vulcnt[node] += vulcnt[e];
    }
}

struct LCA{
    int dp[200005][20];
    void binarylifting(int node,int par)
    {
        dp[node][0] = par;
        for(int i=1;i<20;i++) dp[node][i] = dp[dp[node][i-1]][i-1]; 
        for(auto e:g[node])
        {
            if(e == par) continue;
            binarylifting(e,node);
        }
    }

    int kthparent(int node,int k)
    {
        for(int i=19;i>=0;i--)
        {
            if(k & (1<<i)) node = dp[node][i];
        }
        return node;
    }

    int lca(int u,int v)
    {
        if(depth[u] < depth[v]) swap(u,v);
        u = kthparent(u , depth[u]-depth[v]);
        if(u == v) return v;
        for(int i=19;i>=0;i--)
        {
            if(dp[u][i] == dp[v][i]) continue;
            u = dp[u][i];
            v = dp[v][i];
        }
        return dp[u][0];
    }
    int dist(int u,int v)
    {
        int lcaa = lca(u,v);
        return depth[u]-depth[lcaa] + depth[v]-depth[lcaa];
    }
    int nodeatdis(int u,int v,int d)
    {
        if(d <= depth[u]-depth[lca(u,v)]) return kthparent(u,d);
        return kthparent(v,dist(u,v)-d);
    }
}lca;

int main()
{
    int n; cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=0;i<n-1;i++)
    {
        int u,v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    precal(1,0,0);
    lca.binarylifting(1,0);
    int q; cin >> q;
    while(q--)
    {
        int c,p; cin >> c >> p;
        if(c==p) {cout<<"weee"<<endl; continue;}
        int dis = lca.dist(c,p);
        int x = lca.nodeatdis(c,p,(dis-1)/2);
        int y = lca.nodeatdis(c,p,((dis-1)/2)+1);
        if(depth[x]>depth[y])
        {
            if(vulcnt[x]) cout<<"oops"<<endl;
            else cout<<"weee"<<endl;
        }
        else 
        {
            if(vulcnt[1]-vulcnt[y]) cout<<"oops"<<endl;
            else cout<<"weee"<<endl;
        }
    }
}

Information

Submit By
Type
Submission
Problem
P1134 Terrorist attack in Seriousland
Language
C++17 (G++ 13.2.0)
Submit At
2024-12-12 15:02:21
Judged At
2024-12-12 15:02:21
Judged By
Score
100
Total Time
733ms
Peak Memory
44.996 MiB