/ SeriousOJ /

Record Detail

Runtime Error


  
# Status Time Cost Memory Cost
#1 Accepted 5ms 7.031 MiB
#2 Wrong Answer 3ms 7.031 MiB
#3 Accepted 3ms 7.504 MiB
#4 Accepted 5ms 7.543 MiB
#5 Accepted 4ms 7.504 MiB
#6 Runtime Error 247ms 60.395 MiB

Code

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;

vector<int> g[N];
int table[N + 1][22];
int level[N];
int n, lg, INF = 1e9 + 10;

void dfs(int v, int par = -1, int dep = 0, int mn = INF, int mx = -1) {
    table[v][0] = par;
    level[v] = dep;
    for (int i = 1; i <= lg; i++) {
        if (table[v][i - 1] != -1) {
            table[v][i] = table[table[v][i - 1]][i - 1];
        }
    }
    for (auto &child : g[v]) {
        if (child == par) continue;
        dfs(child, v, dep + 1);
    }
}
void lca_build() { //=> O(n*logn)
    dfs(1);
}
int lca_query(int a, int b) { //=> O(logn)
    if (level[a] < level[b]) swap(a, b);
    // int dis = level[a] - level[b];
    // while (dis)  //a and b come to the same level
    // {
    //     int i = log2(dis);
    //     a = table[a][i], dis -= (1 << i);
    // } 
    for (int i = lg; i >= 0; i--) {  //a and b come to the same level
        if (table[a][i] != -1 && level[table[a][i]] >= level[b])
            a = table[a][i];
    }
    if (a == b) return a;
    for (int i = lg; i >= 0; i--) {
        if (table[a][i] != -1 && table[a][i] != table[b][i])
            a = table[a][i], b = table[b][i];
    }
    return table[a][0];
}
int dist(int u, int v) { // distance between two node
    int l = lca_query(u, v);
    return level[u] + level[v] - (level[l] << 1); //level[l]*2
}
int kth(int u, int k) {
    for (int i = 0; i <= lg; i++)
        if (k & (1 << i)) u = table[u][i];
    return u;
}
int findKth(int u, int v, int k) { // kth node from u to v, 0th node is u
    int l = lca_query(u, v);
    int d = level[u] + level[v] - (level[l] << 1);
    if (level[l] + k <= level[u]) return kth(u, k);
    k -= level[u] - level[l];
    return kth(v, level[v] - level[l] - k);
}

void reset() {
    for (int i = 0; i <= n; i++) {
        g[i].clear();
        level[i] = 0;
        for (int j = 0; j <= lg; j++) table[i][j] = -1;
    }
}

// 0-based indexing, query finds in range [first, last]
#define lg(x) (31 - __builtin_clz(x))
const int K = lg(N);

struct sparse_table {
    ll tr[N][K + 1];

    ll f(ll p1, ll p2) { // Change this function according to the problem.
        return p1 + p2; // <===
    }

    void build(int n, const vector<int> &a) { // O(N * logN)
        for (int i = 0; i < n; i++) {
            tr[i][0] = a[i];
        }
        for (int j = 1; j <= K; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                tr[i][j] = f(tr[i][j - 1], tr[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    ll query1(int l, int r) { // find Sum, LCM => O(LogN)
        ll val = 0; // for sum => val = 0 and lcm => val = 1
        for (int j = K; j >= 0; j--) {
            if ((1 << j) <= r - l + 1) {
                val = f(val, tr[l][j]);
                l += 1 << j;
            }
        }
        return val;
    }

    ll query2(int l, int r) { // find Min, Max, GCD, AND, OR, XOR => O(1)
        int d = lg(r - l + 1);
        return f(tr[l][d], tr[r - (1 << d) + 1][d]);
    }
} spt;


int main() {
    cin >> n;
    lg = log2(n) + 1;

    // memset(table, -1, sizeof table);
    reset();
    vector<int> C(n + 1, 0);
    int tot = 0;
    for(int i = 1; i <= n; i++) cin >> C[i], tot += 2 * C[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);
    }
    lca_build();
    
    vector<int> tin(n + 1), tout(n + 1);
    int time = 0;
    auto dfs = [&](auto&& self, int u, int par) -> void {
        tin[u] = ++time;
        for(auto &v: g[u]) {
            if(v == par) continue;
            self(self, v, u);
        }
        tout[u] = ++time;
    };
    dfs(dfs, 1, 0);

    vector<int> arr(time + 1, 0);
    for(int i = 1; i <= n; i++) {
        arr[tin[i]] = C[i]; 
        arr[tout[i]] = C[i]; 
    }
    spt.build(time + 1, arr);

    // Querys
    int q;
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;
        if(u == v) {
            cout << "weee" << endl;
            continue;
        }
        int d = dist(u, v);
        int mx = findKth(u, v, (d - 1) >> 1);
        int u1 = mx;
        int v1 = findKth(mx, v, 1);
        if(tin[u1] <= tin[u] && tout[u1] >= tout[u]) {
            if(spt.query1(tin[u1], tout[u1]) == 0) cout << "weee" << endl;
            else cout << "oops" << endl;
        }
        else {
            if(tot - spt.query1(tin[v1], tout[v1]) == 0) cout << "weee" << endl;
            else cout << "oops" << endl;
        }
    }
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1134 Terrorist attack in Seriousland
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-29 22:05:55
Judged At
2024-11-29 22:05:55
Judged By
Score
15
Total Time
247ms
Peak Memory
60.395 MiB