oj.uz

Submission #223300

# Submission time Handle Problem Language Result Execution time Memory
223300 2020-04-15T06:58:30 Z dwsc Klasika (COCI20_klasika) C++14
33 / 110
 5000 ms 12452 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 8 ms 4992 KB Output is correct
3 Correct 8 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 9 ms 4992 KB Output is correct
6 Correct 8 ms 4992 KB Output is correct
7 Correct 8 ms 4992 KB Output is correct
8 Correct 8 ms 4992 KB Output is correct
9 Correct 8 ms 4992 KB Output is correct
10 Correct 7 ms 4992 KB Output is correct
11 Correct 7 ms 4992 KB Output is correct
12 Correct 8 ms 4992 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 8 ms 4992 KB Output is correct
3 Correct 8 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 9 ms 4992 KB Output is correct
6 Correct 8 ms 4992 KB Output is correct
7 Correct 8 ms 4992 KB Output is correct
8 Correct 8 ms 4992 KB Output is correct
9 Correct 8 ms 4992 KB Output is correct
10 Correct 7 ms 4992 KB Output is correct
11 Correct 7 ms 4992 KB Output is correct
12 Correct 8 ms 4992 KB Output is correct
13 Correct 10 ms 5152 KB Output is correct
14 Correct 11 ms 5120 KB Output is correct
15 Correct 11 ms 5248 KB Output is correct
16 Correct 11 ms 5248 KB Output is correct
17 Correct 9 ms 5120 KB Output is correct
18 Correct 10 ms 5120 KB Output is correct
19 Correct 10 ms 5120 KB Output is correct
20 Correct 10 ms 5120 KB Output is correct
21 Correct 10 ms 5120 KB Output is correct
22 Correct 10 ms 5120 KB Output is correct
23 Correct 10 ms 5120 KB Output is correct
24 Correct 11 ms 5120 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5074 ms 12452 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 8 ms 4992 KB Output is correct
3 Correct 8 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 9 ms 4992 KB Output is correct
6 Correct 8 ms 4992 KB Output is correct
7 Correct 8 ms 4992 KB Output is correct
8 Correct 8 ms 4992 KB Output is correct
9 Correct 8 ms 4992 KB Output is correct
10 Correct 7 ms 4992 KB Output is correct
11 Correct 7 ms 4992 KB Output is correct
12 Correct 8 ms 4992 KB Output is correct
13 Correct 10 ms 5152 KB Output is correct
14 Correct 11 ms 5120 KB Output is correct
15 Correct 11 ms 5248 KB Output is correct
16 Correct 11 ms 5248 KB Output is correct
17 Correct 9 ms 5120 KB Output is correct
18 Correct 10 ms 5120 KB Output is correct
19 Correct 10 ms 5120 KB Output is correct
20 Correct 10 ms 5120 KB Output is correct
21 Correct 10 ms 5120 KB Output is correct
22 Correct 10 ms 5120 KB Output is correct
23 Correct 10 ms 5120 KB Output is correct
24 Correct 11 ms 5120 KB Output is correct
25 Execution timed out 5074 ms 12452 KB Time limit exceeded
26 Halted 0 ms 0 KB -