/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 4ms 7.027 MiB
#2 Accepted 3ms 7.262 MiB
#3 Accepted 3ms 7.078 MiB
#4 Accepted 3ms 7.07 MiB
#5 Accepted 4ms 9.035 MiB
#6 Accepted 227ms 34.879 MiB
#7 Accepted 335ms 34.82 MiB
#8 Accepted 339ms 34.789 MiB
#9 Accepted 344ms 34.855 MiB
#10 Accepted 335ms 34.828 MiB
#11 Accepted 312ms 34.801 MiB
#12 Accepted 339ms 34.777 MiB
#13 Accepted 324ms 34.793 MiB
#14 Accepted 333ms 34.895 MiB
#15 Accepted 316ms 34.855 MiB
#16 Accepted 340ms 34.879 MiB
#17 Accepted 327ms 34.82 MiB
#18 Accepted 317ms 34.887 MiB
#19 Accepted 340ms 35.121 MiB
#20 Accepted 319ms 34.879 MiB
#21 Accepted 342ms 34.891 MiB
#22 Accepted 453ms 41.191 MiB
#23 Accepted 459ms 41.254 MiB
#24 Accepted 428ms 41.242 MiB
#25 Accepted 443ms 41.094 MiB
#26 Accepted 459ms 41.219 MiB
#27 Accepted 462ms 41.137 MiB
#28 Accepted 721ms 39.238 MiB
#29 Accepted 721ms 39.234 MiB
#30 Accepted 710ms 39.188 MiB
#31 Accepted 361ms 47.363 MiB
#32 Accepted 342ms 47.293 MiB
#33 Accepted 432ms 35.172 MiB
#34 Accepted 463ms 35.172 MiB
#35 Accepted 437ms 35.262 MiB

Code

#include <bits/stdc++.h>
#define endl "\n"
typedef long long ll;
using namespace std;

const int N = 2e5 + 7;
vector<vector<int>> g(N);
int table[N + 1][22];
int level[N], tin[N], tout[N];
int n, lg, Time = 0, INF = 1e9 + 7;

void dfs(int v, int par = -1, int dep = 0) {
    table[v][0] = par;
    level[v] = dep;
    tin[v] = ++Time;
    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);
    }
    tout[v] = ++Time;
}

void lca_build(int root = 1) { //=> O(n*logn)
    dfs(root);
}

int lca_query(int a, int b) { //=> O(logn)
    if (level[a] < level[b]) swap(a, b);
    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() {
    lg = log2(n) + 1;
    for (int i = 0; i <= n; i++) {
        g[i].clear();
        level[i] = 0;
        for (int j = 0; j <= lg; j++) table[i][j] = -1;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    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);
    }
    for(int i = 1; i <= n; i++) {
        if(g[i].size() == 1) {
            lca_build(i);
            break;
        }
    }
    
    vector<int> arr(Time + 1, 0);
    for(int i = 1; i <= n; i++) {
        arr[tin[i]] = C[i]; 
        arr[tout[i]] = C[i]; 
    }
    
    vector<int> pre(Time + 1, 0);
    for(int i = 1; i <= Time; i++) {
        pre[i] = pre[i - 1] + arr[i];
    }
    auto Sum = [&](int l, int r) -> int {
        return pre[r] - pre[l - 1];
    };

    // Querys
    int q;
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;
        if(u == v) {
            cout << "weee" << endl;
            continue;
        }
        int uMx, vMx;
        int d = dist(u, v);
        if(d == 1) {
            uMx = u, vMx = v;
        }
        else {
            uMx = findKth(u, v, (d - 1) >> 1);
            vMx = findKth(uMx, v, 1);
        }

        if(tin[vMx] <= tin[uMx] && tout[vMx] >= tout[uMx]) {
            if(Sum(tin[uMx], tout[uMx]) == 0) cout << "weee" << endl;
            else cout << "oops" << endl;
        }
        else {
            if(tot - Sum(tin[vMx], tout[vMx]) == 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-30 12:56:40
Judged At
2024-12-09 05:05:26
Judged By
Score
100
Total Time
721ms
Peak Memory
47.363 MiB