oj.uz

Submission #465454

# Submission time Handle Problem Language Result Execution time Memory
465454 2021-08-16T07:20:06 Z cs71107 Synchronization (JOI13_synchronization) C++14
10 / 100
 184 ms 19776 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 = 1e5+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 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 10 ms 2140 KB Output is correct
8 Correct 10 ms 2124 KB Output is correct
9 Correct 11 ms 2136 KB Output is correct
10 Correct 180 ms 18648 KB Output is correct
11 Correct 146 ms 18624 KB Output is correct
12 Correct 145 ms 18652 KB Output is correct
13 Correct 135 ms 18280 KB Output is correct
14 Correct 116 ms 17604 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 18316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
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 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 12 ms 2220 KB Output is correct
8 Incorrect 161 ms 19740 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 19776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.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 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 14 ms 2216 KB Output is correct
7 Incorrect 184 ms 19544 KB Output isn't correct
8 Halted 0 ms 0 KB -