/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 7ms 14.605 MiB
#2 Accepted 6ms 15.285 MiB
#3 Accepted 7ms 15.445 MiB
#4 Wrong Answer 6ms 14.102 MiB
#5 Accepted 8ms 15.781 MiB
#6 Wrong Answer 319ms 57.129 MiB

Code

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define bug(a) cout<<#a<<" : "<<a<<endl;
#define bug2(a,b) cout<<#a<<" : "<<a<<"\t"<<#b<<" : "<<b<<endl;

const ll N=3e5+7;
vector<ll>g[N];
const ll LG=18;
ll par[N][LG+1],dep[N],sz[N];
void dfs(ll u,ll p=0)
{
    par[u][0]=p;
    dep[u]=dep[p]+1;
    sz[u]=1;
    for(ll i=1; i<=LG; i++)
    {
        par[u][i]=par[par[u][i-1]][i-1];
    }
    for(auto v:g[u]){
        if(v!=p)
        {
            dfs(v,u);
            sz[u]+= sz[v];
        }
    }
}
ll lca(ll u,ll v)
{
    if(dep[u]<dep[v])
    {
        swap(u,v);
    }
    for(ll k=LG; k>=0; k--)
    {
        if(dep[par[u][k]]>=dep[v])u=par[u][k];
    }
    if(u==v)return u;
    for(ll k=LG; k>=0; k--)
    {
        if(par[u][k]!=par[v][k])u=par[u][k],v=par[v][k];
    }
    return par[u][0];
}
ll dist(ll u,ll v)
{
    ll l=lca(u,v);
    return dep[u]+dep[v]-(dep[l]<<1);
}
vector<ll>v,dis(N,1e9);
ll n;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    ll t=1;
    while(t--){
        cin>>n;
        v.resize(n+1);
        for(ll i=1;i<=n;i++){
            cin>>v[i];
        }
        for(ll i=0;i<n-1;i++){
            ll u,v;cin>>u>>v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        queue<pair<ll,ll>>q;
        for(ll i=1;i<=n;i++){
            if(v[i]==1){
                q.push({i,i});
                dis[i]=0;
            }
        }
        // for(ll i=1;i<=n;i++){
        //     cout<<dis[i]<<' ';
        // }
        vector<ll>par2(N);
        while(!q.empty()){
            auto it=q.front();
            ll u=it.first;
            ll baf=it.second;
            q.pop();
            for(auto v:g[u]){
                // dis[j]=min(dis[j],dis[it.first]+1);
                if(dis[u]+1<dis[v]){
                    par2[v]=baf;
                    dis[v]=dis[u]+1;
                    q.push({v,baf});
                }
            }
        }
        // bug(q.size())
        // for(ll i=1;i<=n;i++){
        //     cout<<dis[i]<<' ';
        // }
        // cout<<endl;
        // for(ll i=1;i<=n;i++){
        //     cout<<par2[i]<<' ';
        // }
        // cout<<endl;
        dfs(1);
        // cout<<dist(3,3)<<endl;
        ll qq;cin>>qq;
        while(qq--){
            ll u,v;cin>>u>>v;
            ll parent=par2[u];
            if(parent==0)parent=u;
            ll diss1=dis[u];
            ll diss2=dist(parent,v);
            // cout<<diss1<<' '<<diss2<<' ';
            // cout<<parent<<endl;
            if(u==v){
                cout<<"weee"<<endl;
                continue;
            }
            if((diss1<diss2)){
                cout<<"oops"<<endl;
            }
            else {
                cout<<"weee"<<endl;
            }
        }
    }
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1134 Terrorist attack in Seriousland
Contest
LU IUJPC : Sylhet Division 2024
Language
C++17 (G++ 13.2.0)
Submit At
2024-12-09 09:22:13
Judged At
2024-12-09 09:22:13
Judged By
Score
12
Total Time
319ms
Peak Memory
57.129 MiB