Submission #223300

#	Time	Username	Problem	Language	Result	Execution time	Memory
223300		dwsc	Klasika (COCI20_klasika)	C++14	33 / 110	5074 ms	12452 KiB

klasika

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
vector<int> adj[200005];
int start[200005],fin[200005];
int num = 0;
void dfs(int u,int pa){
    start[u] = num;
    for (int i = 0; i < adj[u].size(); i++){
        int v = adj[u][i];
        if (v == pa) continue;
        dfs(v,u);
    }
    fin[u] = num++;
}/*
struct node {
    node *l, *r;
    int val;
    int s, m, e, lazyadd;
    node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), val(0), lazyadd(0), l(NULL), r(NULL) {
        if (s != e) l = new node(s, m), r = new node(m+1, e);
    }
    void value() { //returns the value of the current node after lazy propagating
        if (s == e){
            val ^= lazyadd;
            lazyadd = 0;
            return val;
        }
        val ^= lazyadd;
        l->lazyadd ^= lazyadd, r->lazyadd ^= lazyadd;
        lazyadd = 0;
    }
    void add(int x, int y, int v) {
        if (s == x && e == y) lazyadd ^= v;
        else {
            if (x > m) r->add(x, y, v);
            else if (y <= m) l->add(x, y, v);
            else l->add(x, m, v), r->add(m+1, y, v);
            l->value();
            r->value();
            val = max(l->value(), r->value()); //Change here to max
        }
    }
    int query(int x, int y) {
        value();
        if (s == x && e == y) return val;
        if (x > m) return r->query(x, y);
        if (y <= m) return l->query(x, y);
        return max(l->query(x, m),r->query(m+1, y)); //Change here to max
    }
}*root;*/
int arr[200005];
int main(){
    int q;
    cin >> q;
    int n = 1;
    ii que[q];
    int type[q];
    for (int i = 0; i < q; i++){
        string t;
        cin >> t;
        if (t == "Add"){
            int x,w;
            cin >> x >> w;
            x--;
            adj[x].push_back(n);
            que[i] = ii(n,w);
            type[i] = 0;
            n++;
        }
        else{
            int a,b;
            cin >> a >> b;
            a--;
            b--;
            que[i] = ii(a,b);
            type[i] = 1;
        }
    }
    dfs(0,-1);
    for (int i = 0; i < q; i++){
        if (type[i]){
            int a = que[i].first,b = que[i].second;
            int v1 = arr[fin[a]];
            int ans = 0;
            for (int j = start[b]; j <= fin[b]; j++) ans = max(ans,v1^arr[j]);
            cout << ans << "\n";
        }
        else{
            int x = que[i].first, w = que[i].second;
            for (int j = start[x]; j <= fin[x]; j++) arr[j] ^= w;
        }
    }
}

Compilation message (stderr)

klasika.cpp: In function 'void dfs(int, int)':
klasika.cpp:9:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < adj[u].size(); i++){
                     ~~^~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44