oj.uz

답안 #868788

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
868788 2023-11-02T02:25:46 Z Pring Klasika (COCI20_klasika) C++14
0 / 110
 5000 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fs first
#define sc second
#define mp make_pair
typedef pair<int, int> pii;
typedef pair<pii, int> p3i;

const int MXN = 2005;
int n, now = 1, pw[MXN], x[MXN], y[MXN];
vector<pii> edge[MXN];
vector<int> ans;
bitset<MXN> ban;
string s;

int p[MXN], d[MXN], sz[MXN], son[MXN], top[MXN], dfn[MXN], C = 1;

struct BIT {
    int n, val[MXN];
    void init(int _n) {
        n = _n;
        fill(val + 1, val + n + 1, 0);
    }
    void modify(int id, int x) {
        for (; id <= n; id += (id & -id)) val[id] ^= x;
    }
    int query(int id) {
        int ans = 0;
        for (; id > 0; id -= (id & -id)) ans ^= val[id];
        return ans;
    }
    int query(int l, int r) {
        return query(r) ^ query(l - 1);
    }
    void COUT() {
        for (int i = 1; i <= n; i++) cout << val[i] << ' ';
        cout << endl;
    }
} B;

void DFS1(int id, int parent, int depth) {
    p[id] = parent;
    d[id] = depth;
    sz[id] = 1;
    son[id] = -1;
    for (auto &i : edge[id]) {
        if (i.sc == parent) continue;
        DFS1(i.sc, id, depth + 1);
        sz[id] += sz[i.sc];
        if (son[id] == -1) son[id] = i.sc;
        else if (sz[son[id]] < sz[i.sc]) son[id] = i.sc;
    }
    // cout << id << ' ' << son[id] << endl;
}

void DFS2(int id, int parent, int _top) {
    // cout << "DFS2 " << id << ' ' << son[id] << endl;
    top[id] = _top;
    dfn[id] = C++;
    if (son[id] != -1) DFS2(son[id], id, _top);
    for (auto &i : edge[id]) {
        if (i.sc == parent) continue;
        if (i.sc == son[id]) continue;
        DFS2(i.sc, id, i.sc);
    }
}

void BUILD() {
    B.init(now);
    for (int i = 2; i <= now; i++) B.modify(dfn[i], pw[i]);
    // B.COUT();
}

void DFS(int id, int parent, int acc, vector<int> &v) {
    if (ban[id]) return;
    v.push_back(acc);
    for (auto &i : edge[id]) {
        if (i.sc == parent) continue;
        DFS(i.sc, id, acc ^ i.fs, v);
    }
}

inline int CLIMB(int x, int y) {
    int ans = 0;
    if (d[x] < d[y]) swap(x, y);
    while (top[x] != top[y]) {
        ans ^= B.query(dfn[top[x]], dfn[x]);
        x = p[top[x]];
        if (d[x] < d[y]) swap(x, y);
    }
    ans ^= B.query(dfn[top[y]] + 1, dfn[x]);
    return ans;
}

inline int calc(int x, int y) {
    // cout << "calc " << x << ' ' << y << endl;
    vector<int> v;
    DFS(y, p[y], 0, v);
    int xxx = CLIMB(x, y), ans = 0;
    // cout << xxx << endl;
    for (auto &i : v) ans = max(ans, xxx ^ i);
    return ans;
}

void miku() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s >> x[i] >> y[i];
        if (s[0] == 'A') {
            now++;
            edge[now].push_back(mp(y[i], x[i]));
            edge[x[i]].push_back(mp(y[i], now));
            pw[now] = y[i];
        } else {
            y[i] *= -1;
        }
    }
    // for (int i = 1; i <= now; i++) {
    //     for (auto &j : edge[i]) cout << i << ' ' << j.sc << endl;
    // }
    DFS1(1, 0, 0);
    DFS2(1, 0, 1);
    // cout << "PRING" << endl;
    // for (int i = 1; i <= now; i++) cout << dfn[i] << ' ';
    // cout << endl;
    BUILD();
    for (int i = n - 1; i >= 0; i--) {
        if (y[i] > 0) {
            B.modify(dfn[now], pw[now]);
            ban[now] = true;
            now--;
            // B.COUT();
        } else {
            y[i] *= -1;
            // cout << calc(x[i], y[i]) << endl;
            ans.push_back(calc(x[i], y[i]));
        }
    }
    reverse(ans.begin(), ans.end());
    for (auto &i : ans) cout << i << endl;
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    miku();
    return 0;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5060 ms 604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -