/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Wrong Answer 4ms 5.527 MiB
#2 Wrong Answer 3ms 5.793 MiB

Code

#define _GLIBCXX_FILESYSTEM
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

const int N = 2e5+5;

vector<int> g[N];
int up[N][20],d[N];

void dfs(int u,int p = 0,int l = 0) {
    up[u][0] = p;
    d[u] = l;
    for(int i = 1; i < 20; i++) {
        up[u][i] = up[up[u][i-1]][i-1];
    }
    for(auto x: g[u]) {
        if(x == p) continue;
        dfs(x,u,l+1);
    }
}

int binary_lifting(int u,int k) {
    for(int i = 19; i >= 0; i--) {
        if((1 << i) & k) {
            u = up[u][i];
        }
    }
    return u;
}

int lca(int u,int v) {
    if(d[u] < d[v]) swap(u,v);
    u = binary_lifting(u,abs(d[u]-d[v]));
    if(u == v) return u;
    for(int i = 19; i >= 0; i--) {
        if(up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

int dist(int u,int v) {
    int l = lca(u,v);
    return d[u]+d[v]-2*d[l];
}

void solve() {
    int n;
    cin >> n;
    vector<int> v;
    for(int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if(x) v.push_back(i+1);
    }
    for(int i = 1; i < n; i++) {
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1);
    int q;
    cin >> q;
    while(q--) {
        int c,p;
        cin >> c >> p;
        bool ok = 1;
        if(v.size() <= 18000) {
            for(auto x: v) {
                // cerr << x << ' ' << dist(c,x) << ' ' << dist(p,x) << '\n';
                if(dist(c,x) < dist(p,x)) {
                    cout << "oops\n";ok = 0;break;
                }
            }   
        }
        if(ok) cout << "oops\n";
    }
    return;
}

int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int tc = 1;
    // cin >> tc;
    for(int kase = 1; kase <= tc; kase++) {
        //cout << "Case " << kase << ": ";
        solve();
    }
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1134 Terrorist attack in Seriousland
Contest
LU Divisonal Contest Problem Testing Round
Language
C++17 (G++ 13.2.0)
Submit At
2024-12-09 05:33:12
Judged At
2024-12-09 05:33:12
Judged By
Score
0
Total Time
4ms
Peak Memory
5.793 MiB