제출 #1259453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1259453		nmduck6	Synchronization (JOI13_synchronization)	C++20	100 / 100	359 ms	61956 KiB

synchronization

#include <iostream>
#include <iomanip>
#include <cstdint>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>
#include <unordered_map>
#include <stack>

// #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;

struct edge_t {
	int u, v;
	bool operator==(const edge_t& other) const {
		return u == other.u && v == other.v;
	}
};

struct hashedge {
	int64_t operator()(const edge_t& pr) const {
		return (int64_t)pr.u << 32 | pr.v;
	}
};

#define MAXN 100000
#define MAXM 200000

int n, m, q;
vector<int> adj[MAXN + 1];
edge_t edges[MAXN];

int num[MAXN + 1], timer;
int ans[MAXN + 1], prevans[MAXN + 1];
vector<edge_t> sege[(MAXM + 2) * 4 + 1];
int toggles[MAXM + 1];

void dfs(int u, int p) {
	num[u] = ++timer;
	for (int v: adj[u]) {
		if (v == p) continue;
		dfs(v, u);
	}
}

stack<tuple<int, int, int>> st;

int label[MAXN + 1];
int lowest[MAXN + 1];

int findset(int u) {
	return label[u] < 0 ? u : findset(label[u]);
}

void unite(int u, int v) {
	int r = findset(u), s = findset(v);
	if (r == s) return;
	if (-label[r] < -label[s]) swap(r, s);
	st.push({r, label[r], lowest[r]});
	st.push({s, label[s], lowest[s]});
	label[r] += label[s];
	label[s] = r;
	lowest[r] = num[lowest[r]] < num[lowest[s]] ? lowest[r] : lowest[s];
}

int takesnap() {
	return st.size();
}

void rollback(int snap) {
	while ((int)st.size() != snap) {
		auto [u, labelu, lowestu] = st.top(); st.pop();
		label[u] = labelu;
		lowest[u] = lowestu;
	}
}

void update(int node, int nodel, int noder, int l, int r, edge_t& edge) {
	if (r < nodel || l > noder) return;
	if (l <= nodel && noder <= r) {
		sege[node].push_back(edge);
		return;
	}
	int mid = (nodel + noder) >> 1;
	update(node << 1, nodel, mid, l, r, edge);
	update(node << 1 | 1, mid + 1, noder, l, r, edge);
}

int querynode[MAXM + 1];
int reslow[MAXM + 1];
int reslowend[MAXN + 1];

void getqueries(int node, int nodel, int noder) {
	for (auto [u, v]: sege[node]) unite(u, v);
	int snap = takesnap();
	if (nodel == noder) {
		if (nodel == m + 1) {
			for (int i = 1; i <= n; i++) reslowend[i] = lowest[findset(i)];
		}
		if (querynode[nodel])
			reslow[nodel] = lowest[findset(querynode[nodel])];
		return;
	}
	int mid = (nodel + noder) >> 1;
	getqueries(node << 1, nodel, mid);
	rollback(snap);
	getqueries(node << 1 | 1, mid + 1, noder);
	rollback(snap);
}

vector<pair<edge_t, pair<int, int>>> completed;
unordered_map<edge_t, pair<int, int>, hashedge> mp;
bool enabled[MAXN];

void pre() {
	cin >> n >> m >> q;
	fill(label + 1, label + n + 1, -1);
	iota(lowest + 1, lowest + n + 1, 1);
	for (int i = 1; i < n; i++) {
		cin >> edges[i].u >> edges[i].v;
		adj[edges[i].u].push_back(edges[i].v);
		adj[edges[i].v].push_back(edges[i].u);
	}
	for (int i = 1; i <= m; i++) cin >> toggles[i];
}

void run() {
	dfs(1, 1);
	for (int i = 1; i < n; i++) {
		// dam bao thu tu cha con
		if (num[edges[i].u] > num[edges[i].v]) swap(edges[i].u, edges[i].v);
	}
	// disabling edge, prevans[v] = ans[v] = ans[root(u)];
	// enabling edge, ans[root(u)] += ans[v] - prevans[v];
	// -> at each t, get root(u)
	for (int i = 1; i <= m; i++) {
		if (enabled[toggles[i]]) {
			auto& meow = mp[edges[toggles[i]]];
			meow.second = i;
			completed.push_back({edges[toggles[i]], meow});
		} else mp[edges[toggles[i]]] = {i, -1};
		enabled[toggles[i]] = !enabled[toggles[i]];
		querynode[i] = edges[toggles[i]].u;
	}
	for (auto& pr: mp) {
		if (pr.second.second == -1) completed.push_back({pr.first, {pr.second.first, m + 1}});
	}
	for (auto& [edge, pr]: completed) {
		update(1, 1, m + 1, pr.first, pr.second, edge);
	}
	getqueries(1, 1, m + 1);
	fill(enabled + 1, enabled + n, false);
	fill(ans + 1, ans + n + 1, 1);
	for (int i = 1; i <= m; i++) {
		if (enabled[toggles[i]]) prevans[edges[toggles[i]].v] = ans[edges[toggles[i]].v] = ans[reslow[i]];
		else ans[reslow[i]] += ans[edges[toggles[i]].v] - prevans[edges[toggles[i]].v];
		enabled[toggles[i]] = !enabled[toggles[i]];
	}
	while (q--) {
		int u;
		cin >> u;
		cout << ans[reslowend[u]] << '\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();
	}
}

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

컴파일 시 표준 에러 (stderr) 메시지

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

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