/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 5ms 5.035 MiB
#2 Accepted 5ms 7.066 MiB
#3 Accepted 5ms 7.078 MiB
#4 Accepted 5ms 4.992 MiB
#5 Accepted 4ms 5.07 MiB
#6 Accepted 796ms 34.801 MiB
#7 Accepted 810ms 34.773 MiB
#8 Accepted 794ms 34.836 MiB
#9 Accepted 779ms 34.867 MiB
#10 Accepted 772ms 34.855 MiB
#11 Accepted 791ms 34.867 MiB
#12 Accepted 782ms 34.867 MiB
#13 Accepted 785ms 34.832 MiB
#14 Accepted 773ms 34.742 MiB
#15 Accepted 818ms 34.832 MiB
#16 Accepted 783ms 34.668 MiB
#17 Accepted 787ms 34.758 MiB
#18 Accepted 765ms 34.789 MiB
#19 Accepted 799ms 34.844 MiB
#20 Accepted 781ms 34.816 MiB
#21 Accepted 781ms 34.746 MiB
#22 Accepted 1077ms 39.707 MiB
#23 Accepted 1037ms 39.684 MiB
#24 Accepted 1088ms 39.648 MiB
#25 Accepted 1071ms 39.715 MiB
#26 Accepted 1073ms 39.707 MiB
#27 Accepted 1074ms 39.68 MiB
#28 Accepted 1427ms 38.164 MiB
#29 Accepted 1450ms 38.199 MiB
#30 Accepted 1385ms 38.035 MiB
#31 Accepted 944ms 44.297 MiB
#32 Accepted 902ms 44.488 MiB
#33 Accepted 1085ms 35.277 MiB
#34 Accepted 1106ms 35.223 MiB
#35 Accepted 1118ms 35.328 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];
int n, lg, INF = 1e9 + 7;

void dfs(int v, int par = -1, int dep = 0) {
    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(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() {
    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() {
    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);
    }
    for(int i = 1; i <= n; i++) {
        if(g[i].size() == 1) {
            lca_build(i);
            break;
        }
    }
    
    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 + 3, 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 mx, u1, v1;
        int d = dist(u, v);
        if(d == 1) {
            u1 = u, v1 = v;
        }
        else {
            mx = findKth(u, v, (d - 1) >> 1);
            u1 = mx;
            v1 = findKth(mx, v, 1);
        }
        // cout << u1 << " " << v1 << endl;

        if(tin[v1] <= tin[u1] && tout[v1] >= tout[u1]) {
            if(Sum(tin[u1], tout[u1]) == 0) cout << "weee" << endl;
            else cout << "oops" << endl;
        }
        else {
            if(tot - Sum(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-30 12:39:29
Judged At
2024-12-09 05:05:51
Judged By
Score
100
Total Time
1450ms
Peak Memory
44.488 MiB