Submission #465457

#	Time	Username	Problem	Language	Result	Execution time	Memory
465457		cs71107	Synchronization (JOI13_synchronization)	C++14	100 / 100	201 ms	19916 KiB

synchronization

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40