/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 5ms 8.277 MiB
#2 Accepted 4ms 8.816 MiB
#3 Accepted 5ms 6.148 MiB
#4 Accepted 4ms 5.777 MiB
#5 Accepted 5ms 5.934 MiB
#6 Accepted 231ms 27.961 MiB
#7 Accepted 216ms 27.879 MiB
#8 Accepted 217ms 27.828 MiB
#9 Accepted 230ms 28.109 MiB
#10 Accepted 237ms 27.918 MiB
#11 Accepted 235ms 27.762 MiB
#12 Accepted 208ms 27.758 MiB
#13 Accepted 225ms 27.977 MiB
#14 Accepted 239ms 27.785 MiB
#15 Accepted 210ms 27.766 MiB
#16 Accepted 198ms 27.801 MiB
#17 Accepted 183ms 27.773 MiB
#18 Accepted 184ms 27.914 MiB
#19 Accepted 168ms 27.797 MiB
#20 Accepted 163ms 27.965 MiB
#21 Accepted 390ms 27.934 MiB
#22 Accepted 180ms 30.723 MiB
#23 Accepted 160ms 30.594 MiB
#24 Accepted 160ms 30.68 MiB
#25 Accepted 161ms 30.762 MiB
#26 Accepted 170ms 30.785 MiB
#27 Accepted 158ms 30.594 MiB
#28 Accepted 210ms 29.789 MiB
#29 Accepted 196ms 29.949 MiB
#30 Accepted 191ms 29.953 MiB
#31 Accepted 132ms 33.348 MiB
#32 Accepted 146ms 33.184 MiB
#33 Time Exceeded ≥2039ms ≥29.418 MiB
#34 Time Exceeded ≥2033ms ≥29.074 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;
        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:40:19
Judged At
2024-12-09 05:40:19
Judged By
Score
97
Total Time
≥2039ms
Peak Memory
≥33.348 MiB