oj.uz

Submission #337104

# Submission time Handle Problem Language Result Execution time Memory
337104 2020-12-18T13:23:03 Z jhnah917 Synchronization (JOI13_synchronization) C++14
100 / 100
 121 ms 11136 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

struct Node{
    Node *l, *r, *p; int val;
    Node() : Node(1) {}
    Node(int val) : l(nullptr), r(nullptr), p(nullptr), val(val) {}
    bool IsLeft() const { return this == p->l; }
    bool IsRoot() const { return !p || (p->l != this && p->r != this); }
    void Rotate(){
        if(IsRoot()) return;
        if(IsLeft()){
            if(r) r->p = p; p->l = r; r = p;
        }
        else{
            if(l) l->p = p; p->r = l; l = p;
        }
        if(!p->IsRoot()) (p->IsLeft() ? p->p->l : p->p->r) = this;
        auto t = p; p = t->p; t->p = this;
    }
};
void Splay(Node *x){
    for(; !x->IsRoot(); x->Rotate()){
        if(!x->p->IsRoot()){
            if(x->IsLeft() == x->p->IsLeft()) x->p->Rotate();
            else x->Rotate();
        }
    }
}
void Access(Node *x){
    Splay(x); x->r = nullptr;
    for(; x->p; Splay(x)) Splay(x->p), x->p->r = x;
}
void link(Node *p, Node *c){
    Access(c); Access(p);
    c->l = p; p->p = c;
}
void Cut(Node *x){
    Access(x); x->l->p = nullptr; x->l = nullptr;
}
Node* Root(Node *x){
    Access(x); while(x->l) x = x->l;
    Access(x); return x;
}
Node* Par(Node *x){
    Access(x); if(!x->l) return nullptr;
    x = x->l; while(x->r) x = x->r;
    Access(x); return x;
}

int N, M, Q;
int X[202020], Y[202020];

Node nd[202020];
bool chk[202020];
int sum[202020];

void On(int t){
    int a = Root(nd + X[t]) - nd;
    int b = Root(nd + Y[t]) - nd;
    int now = nd[a].val + nd[b].val - sum[t];
    link(nd + X[t], nd + Y[t]);
    a = Root(nd + X[t]) - nd;
    nd[a].val = now;
}
void Off(int t){
    int a = X[t], b = Y[t];
    int rt = Root(nd + a) - nd;
    int now = nd[rt].val;
    if(Par(nd + a) - nd == b) Cut(nd + a);
    else Cut(nd + b);
    sum[t] = now;
    a = Root(nd + a) - nd;
    b = Root(nd + b) - nd;
    nd[a].val = nd[b].val = now;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M >> Q;
    for(int i=1; i<N; i++) cin >> X[i] >> Y[i];
    for(int i=1; i<=M; i++){
        int t; cin >> t; chk[t] ^= 1;
        if(chk[t]) On(t);
        else Off(t);
    }
    for(int i=1; i<=Q; i++){
        int t; cin >> t;
        int rt = Root(nd + t) - nd;
        cout << nd[rt].val << "\n";
    }
}

Compilation message

synchronization.cpp: In member function 'void Node::Rotate()':
synchronization.cpp:19:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   19 |             if(r) r->p = p; p->l = r; r = p;
      |             ^~
synchronization.cpp:19:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   19 |             if(r) r->p = p; p->l = r; r = p;
      |                             ^
synchronization.cpp:22:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   22 |             if(l) l->p = p; p->r = l; l = p;
      |             ^~
synchronization.cpp:22:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   22 |             if(l) l->p = p; p->r = l; l = p;
      |                             ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6636 KB Output is correct
2 Correct 4 ms 6636 KB Output is correct
3 Correct 4 ms 6636 KB Output is correct
4 Correct 4 ms 6636 KB Output is correct
5 Correct 4 ms 6636 KB Output is correct
6 Correct 4 ms 6764 KB Output is correct
7 Correct 9 ms 7020 KB Output is correct
8 Correct 9 ms 7020 KB Output is correct
9 Correct 9 ms 6892 KB Output is correct
10 Correct 87 ms 10240 KB Output is correct
11 Correct 84 ms 10220 KB Output is correct
12 Correct 89 ms 10220 KB Output is correct
13 Correct 63 ms 9836 KB Output is correct
14 Correct 54 ms 9324 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 9736 KB Output is correct
2 Correct 53 ms 9708 KB Output is correct
3 Correct 40 ms 9344 KB Output is correct
4 Correct 40 ms 9324 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6764 KB Output is correct
2 Correct 4 ms 6636 KB Output is correct
3 Correct 5 ms 6636 KB Output is correct
4 Correct 4 ms 6636 KB Output is correct
5 Correct 5 ms 6636 KB Output is correct
6 Correct 5 ms 6764 KB Output is correct
7 Correct 11 ms 7148 KB Output is correct
8 Correct 121 ms 11116 KB Output is correct
9 Correct 95 ms 11116 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 11136 KB Output is correct
2 Correct 67 ms 10476 KB Output is correct
3 Correct 66 ms 10604 KB Output is correct
4 Correct 80 ms 10604 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6636 KB Output is correct
2 Correct 4 ms 6656 KB Output is correct
3 Correct 6 ms 6636 KB Output is correct
4 Correct 4 ms 6636 KB Output is correct
5 Correct 5 ms 6764 KB Output is correct
6 Correct 12 ms 7148 KB Output is correct
7 Correct 114 ms 11116 KB Output is correct
8 Correct 110 ms 11116 KB Output is correct
9 Correct 85 ms 10988 KB Output is correct
10 Correct 111 ms 10732 KB Output is correct
11 Correct 77 ms 10860 KB Output is correct
12 Correct 79 ms 10860 KB Output is correct
13 Correct 66 ms 10604 KB Output is correct