/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 74ms 175.52 MiB
#2 Accepted 74ms 172.242 MiB
#3 Accepted 74ms 172.969 MiB
#4 Accepted 76ms 173.832 MiB
#5 Accepted 75ms 172.781 MiB
#6 Wrong Answer 307ms 185.82 MiB
#7 Wrong Answer 314ms 185.188 MiB

Code

// #pragma GCC optimize("O3,unroll-loops,Ofast")
// #pragma GCC target("avx2")
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
#define int long long
#define endl '\n'

using namespace std;
using pii = pair<int, int>;
using tup = tuple<int, int, int>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// template <class T> using ordered_set = tree<T, null_type,
//                          less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int inf = 1e9;
const int mod = 1000000007;
const double eps = 1e-9;
const int N = 1000005;

void preprocess() {}

int a[N], depth[N];
vector<int> e[N];
int vulsz[N], par[N][19];

void dfs(int i, int p, int dep = 0) {
    vulsz[i] = a[i];
    depth[i] = dep;
    par[i][0] = p;

    for (int j : e[i]) {
        if (j != p) {
            dfs(j, i, dep + 1);
            vulsz[i] += vulsz[j];
        }
    }
}

void sparse(int n) {
    memset(par, -1, sizeof par);
    dfs(1, -1, 0);
    for(int j=1; j<19; j++) {
        for(int i=1; i<=n; i++) {
            if(par[i][j-1] != -1)
                par[i][j] = par[par[i][j-1]][j-1];
        }
    }
}

int lca(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    
    for (int i = 18; i >= 0; i--) {
        if (depth[v] - (1 << i) >= depth[u]) {
            // cout << v << ' ' << (1 << i) << ' ' << par[v][i] << endl;
            v = par[v][i];
        }
    }

    // cout << u << ' ' << v << endl;
    if (u == v) return u;
    
    for (int i = 18; i >= 0; i--) {
        if (par[u][i] != par[v][i]) {
            u = par[u][i];
            v = par[v][i];
        }
    }
    
    return par[u][0];
}

int kthpar(int u, int k) {
    if(depth[u] < k) return -1;

    for(int i=18; i>=0; i--) {
        if((1 << i) <= k) {
            k -= (1 << i);
            u = par[u][i];
        } 
    }

    return u;
}

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

void solve(int tc) {
    int n;
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];

    for(int i=1; i<n; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    memset(par, -1, sizeof par);
    sparse(n);

    int q;
    cin >> q;

    while(q--) {
        int c, p;
        cin >> c >> p;
        if(c == p) {
            cout << "weee" << endl;
            continue;
        }
        if(a[c] or (lca(c, p) != c and vulsz[c])) {
            cout << "oops" << endl;
            continue;
        }
        if(lca(c, p) == c and vulsz[1] - vulsz[kthpar(p, depth[p]-depth[c]-1)] > 0) {
            cout << "oops" << endl;
            continue;
        }

        if(lca(c, p) == c and vulsz[1] == vulsz[p]) {
            cout << "weee" << endl;
            continue;
        }

        int l = lca(c, p), f = 0;

        int lo = 0, hi = depth[c] - depth[l] - 1;
        while(lo <= hi) {
            int mid = lo + hi >> 1;
            int kpar = kthpar(c, mid);
            if(vulsz[kpar] - vulsz[c] > 0) hi = mid - 1;
            else lo = mid + 1;
        }

        if(lo <= depth[c] - depth[l] - 1) {
            int who = kthpar(c, lo);
            if(vulsz[who] - vulsz[c] > 0 and dist(c, who) < dist(who, p)) f = 1;
        }

        lo = 1, hi = depth[p] - depth[l];
        while(lo <= hi) {
            int mid = lo + hi >> 1;
            int kpar = kthpar(p, mid-1);
            if(vulsz[l] - vulsz[kpar] != 0) lo = mid + 1;
            else hi = mid - 1;
        }
        // cout << hi << endl;
        if(hi >= 1 and hi <= depth[p] - depth[l]) {
            int who = kthpar(p, hi);
            if(vulsz[l] - vulsz[who] == 0 and dist(c, who) < dist(who, p)) f = 1;
        }

        if(f) cout << "oops" << endl;
        else cout << "weee" << endl;
    }
}
     
int32_t main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cout.precision(10);

    preprocess(); 

    int T = 1;
    // cin >> T;




    for (int i = 1; i <= T; i++) {
        solve(i);
    }

    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 08:19:25
Judged At
2024-12-09 08:19:25
Judged By
Score
15
Total Time
314ms
Peak Memory
185.82 MiB