Submission #1259316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259316		nmduck6	Synchronization (JOI13_synchronization)	C++20	0 / 100	148 ms	327680 KiB

synchronization

#include <iostream>
#include <iomanip>
#include <cstdint>
#include <algorithm>
#include <vector>
#include <queue>
#include <bitset>

// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")

#define _F ""
// #define MULTITEST

using namespace std;

#define MAXN 100000

// copy chatgpt
struct LCT {
    struct Node {
        Node *l=nullptr, *r=nullptr, *p=nullptr;
        bool rev = false;
        int id;
        Node(int _id=0): id(_id) {}
    };

    vector<Node*> nodes;

    LCT(int n) {
        nodes.resize(n+1);
        for(int i=1;i<=n;i++) nodes[i] = new Node(i);
    }

    // --- utilities ---
    bool is_root(Node* x) {
        return !x->p || (x->p->l!=x && x->p->r!=x);
    }
    void push(Node* x) {
        if(x && x->rev){
            swap(x->l, x->r);
            if(x->l) x->l->rev ^= 1;
            if(x->r) x->r->rev ^= 1;
            x->rev = false;
        }
    }
    void rotate(Node* x){
        Node* p = x->p; Node* g = p->p;
        push(p); push(x);
        if(p->l==x){
            p->l = x->r; if(x->r) x->r->p = p;
            x->r = p;
        } else {
            p->r = x->l; if(x->l) x->l->p = p;
            x->l = p;
        }
        p->p = x; x->p = g;
        if(g){
            if(g->l==p) g->l = x;
            else if(g->r==p) g->r = x;
        }
    }
    void splay(Node* x){
        static vector<Node*> stk;
        stk.clear();
        Node* y=x;
        stk.push_back(y);
        while(!is_root(y)){ y=y->p; stk.push_back(y); }
        while(!stk.empty()){ push(stk.back()); stk.pop_back(); }

        while(!is_root(x)){
            Node* p=x->p; Node* g=p->p;
            if(!is_root(p)){
                if((p->l==x) ^ (g->l==p)) rotate(x);
                else rotate(p);
            }
            rotate(x);
        }
    }
    void access(Node* x){
        Node* last=nullptr;
        for(Node* y=x; y; y=y->p){
            splay(y);
            y->r = last;
            last = y;
        }
        splay(x);
    }
    void make_root(Node* x){
        access(x);
        x->rev ^= 1;
        push(x);
    }
    Node* find_root(Node* x){
        access(x);
        while(x->l){ push(x); x=x->l; }
        splay(x);
        return x;
    }

    // --- public interface ---
    void make_tree(int v) { /* already init in constructor */ }

    void link(int u,int v){
        Node* x = nodes[u];
        Node* y = nodes[v];
        make_root(x);
        if(find_root(y) != x){ // only if different components
            x->p = y;
        }
    }
    void cut(int u,int v){
        Node* x = nodes[u];
        Node* y = nodes[v];
        make_root(x);
        access(y);
        // now x is root, y is splayed
        if(y->l == x && !x->r){
            y->l->p = nullptr;
            y->l = nullptr;
        }
    }
    int representative(int u){
        return find_root(nodes[u])->id;
    }
};

struct edge_t {
	int u, v;
};

int n, m, q;
edge_t edges[MAXN];
bool enabled[MAXN + 1];
bitset<MAXN> conn[MAXN + 1];

void pre() {
	cin >> n >> m >> q;
	for (int i = 1; i < n; i++) cin >> edges[i].u >> edges[i].v;
}

void run() {
	for (int i = 1; i <= n; i++) conn[i][i - 1] = true;
	LCT lct(n);
	while (m--) {
		int ind;
		cin >> ind;
		auto [u, v] = edges[ind];
		if (enabled[ind]) {
			bitset<MAXN>& bs = conn[lct.representative(u)];
			lct.cut(u, v);
			conn[lct.representative(u)] = bs;
			conn[lct.representative(v)] = bs;
		} else {
			bitset<MAXN>& bs = conn[lct.representative(u)];
			bs |= conn[lct.representative(v)];
			lct.link(u, v);
			conn[lct.representative(u)] = bs;
		}
		enabled[ind] = !enabled[ind];
	}
	while (q--) {
		int k;
		cin >> k;
		cout << conn[k].count() << '\n';
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	if (fopen(_F".inp", "r")) {
		freopen(_F".inp", "r", stdin);
		freopen(_F".out", "w", stdout);
	}
	pre();
	int t = 1;
	#ifdef MULTITEST
	cin >> t;
	#endif
	while (t--) {
		run();
	}
}

/*
                                      #++*                                                          
                                  *-----::--+%                                                      
                                *---::---::--=------------=+##       %%%#                           
                               +-:::::-===-------::::::::::::::=*+-:--::::-+%                       
                             +-::::-=:::::::::::::::::::::--=-::::==:::::::::-*                     
               *#           #=::---::::::::::::::::::::::::::::--:::------:::::=*                   
             ##**          #=:--:::::::::::::::::::::::::::::::::--::::=-::-::::+                   
             #             +:--:::::::::::-::::::::::::::::::::::::--:::--:::-:::*                  
               *          *-+:::::::::::-:::::::::::::::--:::::::::::-:::--:::::::*                 
             **          #==::::::::::--::::::::::::::::::-:::::::::::-::--=:::-::=                 
              *  *       *+::::::::::-:::::::::::::::::::::-:::::::::::--::-=:::-:-+                
            **#          *-:::::::::-:::::::::::::::::::::-:::::::::::::--:::=:::-:-#               
                        *=:::::::::-::::::::::::::::::::::::-::::::::::::-::---:::--*               
                ***     +:::::::::-:::::::::::==:::::::::::::=::::::::::::-:--=::::-+               
                 *     *-::::::::--::::::::::-::--::::::::::::-:::::::::::---:--:::-=               
                       +:::::::::=:::::-:::-::::::-:-::::::::-=::::::::::::--:-=-:::=               
                      *-::::::::--:::-:::--::::::::=:-::::::::=-:::::::::::=-:-=-:::=               
                      +:::::::::=::-:::--::::::::::::=-:::::::-=::::::::::::=:==--::=               
         *====+**    #=:::::::::=-:--=--::-:::::::::::---::::::-::::::::::::=-==--::=               
         *-:::::::--:--:-::::::===-:-::::-::::::::::-:::-==-:::--:::::::::::+-==--::=               
          =-:----------:-::::::-::::::::::::::::::::::--:--:-===-:-:::::::::+==----:=               
            =-:----::--:-::::::-:::::::::::::::::::::::::::::::--:-:::::::::+:::::-==++*##          
              *-:--::----::::::-:::::::::::::::::::::::::::::::--:-:::::::::=--------:::::::-*      
                +-------=::::::-::=####*=::::::::::::::::::::::-::::::::::::-:----------::-=*       
                   +==--*::::::=:::::::::::::::::::::=###*+-:::=:-:::::::-:=---------::--=          
                      +-*=:::::-::::::::::::::::::::::::::=*-::-::::::::-+:=---:--::=+              
                      *:*+-:::::=:::::::::::::::::::::::::::::=:::::::::+-==-::-=+=-=               
                       *=++-::---=:::::::::::::::::::::::::::=:--:::::-+=-=-=+=====-=+              
                       ++*=*=::-===:::::::::::::::::::::::::---=-::::=++=+======------+             
                       =+=+*-=+=-==:::::::::::::::::::::::-==*=-:::-+++=--------=+==+++*            
                      #-*=*+----==++::::::::::-=:::::::::::-==-::=+*=------------=-----=+           
                      *+==*=--------=+=-:::::--======++++--=====----=------------==----=+           
                      +=-------------===+=--------------==-----------=------------=-----=*          
                     *=------------==--------------------=-----------=====--------=-----=+          
                    *=-------------==---------------------=----------=+====-------==+**++*          
                    *=-------------==----------------------=---------=====--------==---==+          
                    *=-------------==--------------------=++----------==----------=======+          
                    #+=------------==------------------=+==-----------=----------==-=====+          
                    +====-----------=----------------=+=====----------=---------=========*          
                    +--:+*+---------+----------------*====-==---------+==------==+=+*+==*           
                   *:-::++=-+==-----=+---------------===---==-----==+*#**=-=+==+++===+              
                   +:-::++-::::-=====+=--------------------==-==++++++++::--::::-+++=+              
                  #::-::++-::::::::::+#------------------=++++=--::-++=::-:::::::-+-=#              
                  *::-::++-::::::::-++*+---------------=++--::::::=++=::-:::::::::-+-*              
                 #-::-::++-:::::::-+++:-=------------=++--:::::::=++=::=:::::::::::==+              
                 *:::--:++=::::::=++-::=+=---------=++--::::::::-+++::-::::::::::::==+              
                 +:::-::=+=::::-+++-::---==-----=++**-:::::::::-+++::-:::::::::::::-==#             
                 =::::-:-++-::-+++::--::::::----*:-++=:::::::::+++::--::::::::::::::=-*             
                #-::::=::++-:-++=::-:::::::::::::::=++-:::::::+++-::-:::::::::::::::+-+             
                *-::::-::=+==++-::-::::::::::::::-::++=::::::=++=::=::::::::::::::::==-*            
                *-:::::-:-++++=::-::::::::::::::::-::++=::::-++=::=:::::::::::::::::-=-+            
                   ::::::-+++=:::::::::::::::::::::::=++-:::=++-:::::::::::::::::::::--             
*/

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:173:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |                 freopen(_F".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:174:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |                 freopen(_F".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40