/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 5ms 7.039 MiB
#2 Accepted 6ms 7.031 MiB
#3 Accepted 7ms 6.992 MiB
#4 Accepted 5ms 7.219 MiB
#5 Accepted 6ms 7.125 MiB
#6 Accepted 729ms 34.738 MiB
#7 Accepted 733ms 34.75 MiB
#8 Accepted 734ms 34.848 MiB
#9 Accepted 741ms 34.832 MiB
#10 Accepted 717ms 34.797 MiB
#11 Accepted 727ms 34.785 MiB
#12 Accepted 739ms 34.77 MiB
#13 Accepted 730ms 34.758 MiB
#14 Accepted 748ms 34.855 MiB
#15 Accepted 751ms 34.855 MiB
#16 Accepted 757ms 34.84 MiB
#17 Accepted 723ms 34.715 MiB
#18 Accepted 727ms 34.812 MiB
#19 Accepted 736ms 34.785 MiB
#20 Accepted 732ms 34.863 MiB
#21 Accepted 743ms 34.816 MiB
#22 Accepted 1030ms 41.16 MiB
#23 Accepted 1054ms 41.16 MiB
#24 Accepted 1087ms 41.215 MiB
#25 Accepted 1070ms 41.23 MiB
#26 Accepted 1068ms 41.203 MiB
#27 Accepted 1102ms 41.152 MiB
#28 Accepted 1396ms 39.219 MiB
#29 Accepted 1470ms 39.211 MiB
#30 Accepted 1472ms 39.176 MiB
#31 Accepted 887ms 47.332 MiB
#32 Accepted 910ms 47.324 MiB
#33 Accepted 1103ms 35.312 MiB
#34 Accepted 1076ms 35.34 MiB
#35 Accepted 1061ms 35.148 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() {
    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:47:10
Judged At
2024-12-09 05:05:28
Judged By
Score
100
Total Time
1472ms
Peak Memory
47.332 MiB