oj.uz

Submission #465457

# Submission time Handle Problem Language Result Execution time Memory
465457 2021-08-16T07:26:28 Z cs71107 Synchronization (JOI13_synchronization) C++14
100 / 100
 201 ms 19916 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

struct Node{

    Node *L,*R,*p;

    int cnt;
    int v;
    int vv;
    int idx;

    bool rev;

    Node(int idx_,int v_,Node *p) : idx(idx_),v(v_),p(p){
        L = R = nullptr;
        cnt = 1;
        vv = v_;
        rev = false;
    }

    Node(int idx_,int vv_): Node(idx_,vv_,nullptr){}

    Node(int idx_): Node(idx_,INF,nullptr){}

    Node() : Node(0,INF,nullptr){}

    /*
    ~Node(){
        if(L) delete L;
        if(R) delete R;
    }*/
};

struct LinkCutTree{

    Node* ptr[MAXN*3];

    bool chk_root(Node *x){
        if(!(x->p))return true;
        else if((x->p->L)!=x && (x->p->R)!=x)return true;
        else return false;
    }

    void Update_lazy(Node *x){
        if(!x)return;

        if(!(x->rev))return;

        swap(x->L,x->R);

        if(x->L)x->L->rev = !x->L->rev;
        if(x->R)x->R->rev = !x->R->rev;
        x->rev = false;
    }

    void Update(Node *x){

        x->cnt = 1;
        x->vv = x->v;

        if(x->L) {
            x->cnt += x->L->cnt;
            x->vv = max(x->vv,x->L->vv);
        }
        if(x->R) {
            x->cnt += x->R->cnt;
            x->vv = max(x->vv,x->R->vv);
        }
    }

    void Rotate(Node *x){

        Node *p = x->p;

        if(!p)return;

        if(x == p->R){
            p->R = x->L;
            x->L = p;

            if(p->R){
                p->R->p = p;
            }
        }
        else {
            p->L = x->R;
            x->R = p;

            if(p->L){
                p->L->p = p;
            }
        }

        x->p = p->p;
        p->p = x;

        if(x->p){
            if(p == (x->p->L))x->p->L = x;
            else if(p== (x->p->R))x->p->R = x;
        }

        Update(p);
        Update(x);
    }

    void Splay(Node *x){

        while(!chk_root(x)){
            Node *p = x->p;

            if(!chk_root(p))Update_lazy(p->p);

            Update_lazy(p);
            Update_lazy(x);

            if(!chk_root(p)){
                if((x== (p->L)) != (p == (p->p->L)))Rotate(x);
                else Rotate(p);
            }

            Rotate(x);
        }

        Update_lazy(x);
    }

    void Update_v(Node *x,int v_){

        Splay(x);

        x->v = v_;

        Update(x);
    }

    Node* Access(Node *x){

        Splay(x);

        x->R = nullptr;

        Update(x);

        Node *cur = x;

        while(x->p){

            Node *p = x->p;

            cur = p;

            Splay(p);

            p->R = x;

            Update(p);

            Splay(x);
        }

        return cur;
    }

    void Link(Node *x,Node *y){//x will be parrent of y

        Access(x);
        Access(y);

        y->L = x;

        x->p = y;

        Update(y);
    }

    void Cut(Node *x){
        Access(x);

        if(!(x->L))return;

        x->L->p = nullptr;
        x->L = nullptr;

        Update(x);
    }

    void Make_root(Node *x){
        Access(x);

        x->rev = !(x->rev);
    }

    Node* Get_root(Node *x){
        Access(x);

        while(x->L){
            x = x->L;
        }

        Splay(x);

        return x;
    }

    Node* Get_parrent(Node *x){
        Access(x);

        if(!(x->L))return nullptr;

        x = x->L;

        while(x->R){
            x = x->R;
        }

        Splay(x);

        return x;
    }

    Node* Get_lca(Node *x,Node *y){
        Access(x);

        return Access(y);
    }

    int Get_depth(Node *x){
        Access(x);

        if(x->L)return x->L->cnt;
        else return 0;
    }

    int Get_max(Node *x,Node *y){

        Node *lc = Get_lca(y,x);

        Access(x);
        Splay(lc);

        int res = (lc->v);

        if(lc->R){
            res = max(res,lc->R->vv);
        }

        Access(y);
        Splay(lc);

        if(lc->R){
            res = max(res,lc->R->vv);
        }

        return res;
    }

    void init(int n,int m){

        for(int i=1;i<=n;i++){
            ptr[i] = new Node(i,1);
        }

        for(int i=1;i<=m;i++){
            ptr[i+n] = new Node(i,0);
        }

        return;
    }

    void er(int n){

        for(int i=1;i<=n;i++){
            delete ptr[i];
        }

        return;
    }

}tree;

pii edge[MAXN];
int chk[MAXN];
int A[MAXN];
int query[MAXN];

int main()
{
    int n,m,k,a,b,x,y,q;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1,idy = -1;
    int tc;
    int sz;
    int ty;
    int va,vb,vc;

    Node *xnode = nullptr;
    Node *ynode = nullptr;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>m>>q;

    for(int i=1;i<n;i++){
        cin>>edge[i].f>>edge[i].s;
    }

    for(int i=0;i<m;i++){
        cin>>query[i];
    }

    for(int i=0;i<q;i++){
        cin>>A[i];
    }

    tree.init(n,n-1);

    for(int i=0;i<m;i++){

        idx = query[i];

        a = edge[idx].f;
        b = edge[idx].s;

        if(chk[idx]){

            xnode = tree.Get_root(tree.ptr[n+idx]);

            tree.Splay(xnode);

            cur = (xnode->vv);

            tree.Make_root(tree.ptr[a]);

            tree.Cut(tree.ptr[n+idx]);

            tree.Cut(tree.ptr[b]);

            tree.Make_root(tree.ptr[a]);
            tree.Make_root(tree.ptr[b]);

            tree.Update_v(tree.ptr[a],cur);
            tree.Update_v(tree.ptr[b],cur);
            tree.Update_v(tree.ptr[n+idx],cur);
        }
        else {

            xnode = tree.Get_root(tree.ptr[a]);
            ynode = tree.Get_root(tree.ptr[b]);

            tree.Splay(xnode);
            tree.Splay(ynode);

            va = (xnode->vv);
            vb = (ynode->vv);

            vc = (tree.ptr[n+idx]->vv);

            cur = va+vb-vc;

            tree.Make_root(tree.ptr[b]);

            tree.Link(tree.ptr[n+idx],tree.ptr[b]);
            tree.Link(tree.ptr[a],tree.ptr[n+idx]);

            xnode = tree.Get_root(tree.ptr[a]);

            tree.Update_v(xnode,cur);
        }
        chk[idx]^=1;
    }

    for(int i=0;i<q;i++){
        idx = A[i];

        xnode = tree.Get_root(tree.ptr[idx]);

        cur = (xnode->vv);

        cout<<cur<<"\n";
    }

    tree.er((n<<1)-1);

    return 0;
}

Compilation message

synchronization.cpp: In constructor 'Node::Node(int, int, Node*)':
synchronization.cpp:29:9: warning: 'Node::idx' will be initialized after [-Wreorder]
   29 |     int idx;
      |         ^~~
synchronization.cpp:27:9: warning:   'int Node::v' [-Wreorder]
   27 |     int v;
      |         ^
synchronization.cpp:33:5: warning:   when initialized here [-Wreorder]
   33 |     Node(int idx_,int v_,Node *p) : idx(idx_),v(v_),p(p){
      |     ^~~~
synchronization.cpp:27:9: warning: 'Node::v' will be initialized after [-Wreorder]
   27 |     int v;
      |         ^
synchronization.cpp:24:17: warning:   'Node* Node::p' [-Wreorder]
   24 |     Node *L,*R,*p;
      |                 ^
synchronization.cpp:33:5: warning:   when initialized here [-Wreorder]
   33 |     Node(int idx_,int v_,Node *p) : idx(idx_),v(v_),p(p){
      |     ^~~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:307:13: warning: unused variable 'k' [-Wunused-variable]
  307 |     int n,m,k,a,b,x,y,q;
      |             ^
synchronization.cpp:307:19: warning: unused variable 'x' [-Wunused-variable]
  307 |     int n,m,k,a,b,x,y,q;
      |                   ^
synchronization.cpp:307:21: warning: unused variable 'y' [-Wunused-variable]
  307 |     int n,m,k,a,b,x,y,q;
      |                     ^
synchronization.cpp:308:9: warning: unused variable 'mx' [-Wunused-variable]
  308 |     int mx = 0;
      |         ^~
synchronization.cpp:309:9: warning: unused variable 'mn' [-Wunused-variable]
  309 |     int mn = INF;
      |         ^~
synchronization.cpp:310:27: warning: unused variable 'idy' [-Wunused-variable]
  310 |     int cur = 0, idx = -1,idy = -1;
      |                           ^~~
synchronization.cpp:311:9: warning: unused variable 'tc' [-Wunused-variable]
  311 |     int tc;
      |         ^~
synchronization.cpp:312:9: warning: unused variable 'sz' [-Wunused-variable]
  312 |     int sz;
      |         ^~
synchronization.cpp:313:9: warning: unused variable 'ty' [-Wunused-variable]
  313 |     int ty;
      |         ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 10 ms 1952 KB Output is correct
8 Correct 10 ms 1868 KB Output is correct
9 Correct 11 ms 1952 KB Output is correct
10 Correct 156 ms 16296 KB Output is correct
11 Correct 176 ms 16324 KB Output is correct
12 Correct 143 ms 16276 KB Output is correct
13 Correct 123 ms 16324 KB Output is correct
14 Correct 111 ms 15904 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 16336 KB Output is correct
2 Correct 82 ms 18152 KB Output is correct
3 Correct 66 ms 17704 KB Output is correct
4 Correct 66 ms 17588 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 13 ms 1996 KB Output is correct
8 Correct 175 ms 16916 KB Output is correct
9 Correct 178 ms 19776 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 16952 KB Output is correct
2 Correct 99 ms 19024 KB Output is correct
3 Correct 94 ms 19264 KB Output is correct
4 Correct 94 ms 19280 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 13 ms 1996 KB Output is correct
7 Correct 182 ms 17044 KB Output is correct
8 Correct 188 ms 19812 KB Output is correct
9 Correct 133 ms 19712 KB Output is correct
10 Correct 201 ms 19260 KB Output is correct
11 Correct 111 ms 19880 KB Output is correct
12 Correct 112 ms 19916 KB Output is correct
13 Correct 95 ms 19276 KB Output is correct