/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 7ms 13.527 MiB
#2 Accepted 7ms 13.336 MiB
#3 Accepted 8ms 10.977 MiB
#4 Wrong Answer 5ms 11.254 MiB
#5 Accepted 7ms 12.383 MiB
#6 Wrong Answer 261ms 36.602 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 int N=3e5+7;
vector<int>g[N];
const int LG=18;
int par[N][LG+1],dep[N],sz[N];
void dfs(int u,int p=0)
{
    par[u][0]=p;
    dep[u]=dep[p]+1;
    sz[u]=1;
    for(int 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];
        }
    }
}
int lca(int u,int v)
{
    if(dep[u]<dep[v])
    {
        swap(u,v);
    }
    for(int k=LG; k>=0; k--)
    {
        if(dep[par[u][k]]>=dep[v])u=par[u][k];
    }
    if(u==v)return u;
    for(int k=LG; k>=0; k--)
    {
        if(par[u][k]!=par[v][k])u=par[u][k],v=par[v][k];
    }
    return par[u][0];
}
int dist(int u,int v)
{
    int l=lca(u,v);
    return dep[u]+dep[v]-(dep[l]<<1);
}
vector<int>v,dis(N,1e9);
int n;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t=1;
    while(t--){
        cin>>n;
        v.resize(n+1);
        for(int i=1;i<=n;i++){
            cin>>v[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);
        }
        queue<pair<int,int>>q;
        for(int i=1;i<=n;i++){
            if(v[i]==1){
                q.push({i,i});
                dis[i]=0;
            }
        }
        // for(int i=1;i<=n;i++){
        //     cout<<dis[i]<<' ';
        // }
        vector<int>par2(N);
        while(!q.empty()){
            auto it=q.front();
            int u=it.first;
            int 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(int i=1;i<=n;i++){
        //     cout<<dis[i]<<' ';
        // }
        // cout<<endl;
        // for(int i=1;i<=n;i++){
        //     cout<<par2[i]<<' ';
        // }
        cout<<endl;
        dfs(1);
        // cout<<dist(1,5)<<endl;
        int qq;cin>>qq;
        while(qq--){
            int u,v;cin>>u>>v;
            int parent=par2[u];
            int diss1=dis[u];
            int diss2=dist(parent,v);
            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:15:23
Judged At
2024-12-09 09:15:23
Judged By
Score
12
Total Time
261ms
Peak Memory
36.602 MiB