Submission #415421

#TimeUsernameProblemLanguageResultExecution timeMemory
415421oolimry다리 (APIO19_bridges)C++17
100 / 100
1767 ms16408 KiB
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
#define show3(x, y, z) cerr << #x << " is " << x << ", " << #y << " is " << y << ", " << #z << " is " << z << endl;
#define rint register int 
typedef long long lint;
typedef pair<int, int> ii;
const int UPD = 1;
const int QRY = 2;
 
int edgeW[100005];
int U[100005];
int V[100005]; ///if B == -1, then is query
vector<ii> history[100005];
int n, m, Q;
 
int T[100005];
int queryW[100005];
int X[100005];
int ans[100005];
 
 
int p[50005];
int sz[50005];
int rak[50005];
inline void reset(){
	for(rint i = 1;i <= n;i++) p[i] = i, sz[i] = 1, rak[i] = 0;
}
 
inline int findSet(int u){
	if(p[u] == u) return u;
	else return p[u] = findSet(p[u]);
}
 
inline void unionSet(int u, int v){
	u = findSet(u), v = findSet(v);
	if(u == v) return;
	
	if(rak[u] > rak[v]) swap(u,v);
	
	if(rak[u] == rak[v]) rak[v]++;
	p[u] = v;
	sz[v] += sz[u];
}
 
bool changed[100005];
vector<int> order;
vector<int> neworder;
int ptr = 1;
inline void catchup(int limit){
	vector<int> C;
	for(;ptr <= limit;ptr++){
		if(T[ptr] == UPD){
			edgeW[X[ptr]] = queryW[ptr];
			C.push_back(X[ptr]);
			changed[X[ptr]] = true;
		}
	}
	
	sort(all(C), [&](int a, int b){ return edgeW[a] > edgeW[b]; });
	C.erase(unique(all(C)), C.end());
	
	auto it = order.begin();
	for(rint e : C){
		int w = edgeW[e];
		while(it != order.end()){
			if(changed[*it]){
				it++;
				continue;
			}
			if(edgeW[*it] < w) break;
			else neworder.push_back(*it);
			it++;
		}
		neworder.push_back(e);
	}
	while(it != order.end()){
		if(not changed[*it]) neworder.push_back(*it);
		it++;
	}
	
	for(rint e : C) changed[e] = false;
	swap(order,neworder); neworder.clear();	
}
 
vector<int> adj[50005];
bool vis[50005];
 
int dfs(int u){
	int res = sz[u];
	vis[u] = true;
	for(int v : adj[u]){
		if(not vis[v]){
			res += dfs(v);
		}
	}
	return res;
}
 
 
inline void solve(int L, int R){
	catchup(L);
	
	vector<int> stuff;
	vector<int> changededges;
	for(int i = L;i <= R;i++){
		stuff.push_back(i);
		if(T[i] == UPD) changededges.push_back(X[i]);
	}
	
	for(int x : changededges) changed[x] = true;
	
	reset();
	sort(all(stuff), [&](int a, int b){ return queryW[a] > queryW[b]; });
	
	auto it = order.begin();
	for(int qid : stuff){ ///decreasing w
		int w = queryW[qid];
		if(T[qid] == UPD) continue;
		
		while(it != order.end()){
			if(edgeW[*it] < w) break;
			else{
				int e = *it;
				if(not changed[e]){
					unionSet(U[e], V[e]);
				}
				it++;
			}
		}
		
		///if is query
		vector<int> special;
		for(int e : changededges){
			auto it = upper_bound(all(history[e]), ii(qid,-1)); it--;
			if(it->second < w) continue; ///edge weight not enough to handle car weight
			
			int u = findSet(U[e]), v = findSet(V[e]);
			if(u == v){
				special.push_back(u);
			}
			else{
				adj[u].push_back(v);
				adj[v].push_back(u);
				special.push_back(u);
				special.push_back(v);
			}
		}
		
		int source = findSet(X[qid]);
		special.push_back(source);
		
		int res = dfs(source);
		ans[qid] = res;
		
		///reset the stuff
		for(int u : special) vis[u] = false, adj[u].clear();
	}
	///reset the stuff
	for(int e : changededges) changed[e] = false;
}
 
const int B1 = 400; ///minimum size to proceed
const int B2 = 250; ///max number of updates to handle
int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> m;
	for(rint i = 1;i <= m;i++) cin >> U[i] >> V[i] >> edgeW[i];
	sort(all(order), [&](int a, int b){ return edgeW[a] > edgeW[b]; });
	cin >> Q;
	for(rint i = 1;i <= Q;i++) cin >> T[i] >> X[i] >> queryW[i];
	
	order.resize(m);
	for(rint i = 1;i <= m;i++) order[i-1] = i;
	sort(all(order), [&](int a, int b){ return edgeW[a] > edgeW[b]; });
	 
	for(rint i = 1;i <= m;i++) history[i].push_back(ii(0, edgeW[i]));
	for(rint i = 1;i <= Q;i++){
		if(T[i] == UPD) history[X[i]].push_back(ii(i, queryW[i]));
	}
	
	///bruh prunning
	int L = -1, R = -1, cnt = 0;
	for(rint i = 1;i <= Q;i++){
		if(L == -1){
			if(T[i] == QRY) L = i, R = i;
		}
		else{
			if(T[i] == UPD) cnt++;
			else R = i;
		}
		
		if((R-L+1 >= B1 and cnt >= B2) or i == Q){
			solve(L,R);
			cnt = 0, L = -1, R = -1;
		}
	}
	
	for(rint i = 1;i <= Q;i++){
		if(T[i] == QRY) cout << ans[i] << '\n';
	}
}

Compilation message (stderr)

bridges.cpp: In function 'void reset()':
bridges.cpp:30:11: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   30 |  for(rint i = 1;i <= n;i++) p[i] = i, sz[i] = 1, rak[i] = 0;
      |           ^
bridges.cpp: In function 'void catchup(int)':
bridges.cpp:67:11: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   67 |  for(rint e : C){
      |           ^
bridges.cpp:85:11: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   85 |  for(rint e : C) changed[e] = false;
      |           ^
bridges.cpp: In function 'int main()':
bridges.cpp:173:11: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  173 |  for(rint i = 1;i <= m;i++) cin >> U[i] >> V[i] >> edgeW[i];
      |           ^
bridges.cpp:176:11: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  176 |  for(rint i = 1;i <= Q;i++) cin >> T[i] >> X[i] >> queryW[i];
      |           ^
bridges.cpp:179:11: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  179 |  for(rint i = 1;i <= m;i++) order[i-1] = i;
      |           ^
bridges.cpp:182:11: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  182 |  for(rint i = 1;i <= m;i++) history[i].push_back(ii(0, edgeW[i]));
      |           ^
bridges.cpp:183:11: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  183 |  for(rint i = 1;i <= Q;i++){
      |           ^
bridges.cpp:189:11: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  189 |  for(rint i = 1;i <= Q;i++){
      |           ^
bridges.cpp:204:11: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  204 |  for(rint i = 1;i <= Q;i++){
      |           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...