/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 3ms 5.57 MiB
#2 Accepted 3ms 5.777 MiB
#3 Accepted 3ms 6.027 MiB
#4 Accepted 3ms 5.504 MiB
#5 Accepted 3ms 5.297 MiB
#6 Accepted 235ms 27.82 MiB
#7 Accepted 219ms 28.055 MiB
#8 Accepted 205ms 27.766 MiB
#9 Accepted 224ms 27.77 MiB
#10 Accepted 236ms 28.152 MiB
#11 Accepted 241ms 27.766 MiB
#12 Accepted 221ms 28.152 MiB
#13 Accepted 206ms 28.074 MiB
#14 Accepted 205ms 27.77 MiB
#15 Accepted 206ms 27.762 MiB
#16 Accepted 195ms 27.852 MiB
#17 Accepted 192ms 27.949 MiB
#18 Accepted 173ms 27.77 MiB
#19 Accepted 176ms 28.012 MiB
#20 Accepted 166ms 27.902 MiB
#21 Accepted 384ms 28.184 MiB
#22 Accepted 182ms 30.949 MiB
#23 Accepted 162ms 30.781 MiB
#24 Accepted 172ms 30.785 MiB
#25 Accepted 162ms 30.566 MiB
#26 Accepted 170ms 30.605 MiB
#27 Accepted 158ms 30.676 MiB
#28 Accepted 206ms 29.859 MiB
#29 Accepted 206ms 30.062 MiB
#30 Accepted 204ms 29.875 MiB
#31 Accepted 133ms 33.184 MiB
#32 Accepted 155ms 33.316 MiB
#33 Time Exceeded ≥2034ms ≥29.445 MiB
#34 Time Exceeded ≥2096ms ≥29.418 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() == n) {
            if(c == p) cout << "weee\n";
            else cout << "oops\n";
            continue;
        }
        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 << "weee\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:43:13
Judged At
2024-12-09 05:43:13
Judged By
Score
97
Total Time
≥2096ms
Peak Memory
≥33.316 MiB