Submission #398369

#	Time	Username	Problem	Language	Result	Execution time	Memory
398369		oolimry	Bridges (APIO19_bridges)	C++17	100 / 100	1677 ms	13656 KiB

bridges

#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;
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(int 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(int 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(int 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(int 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(int i = 1;i <= Q;i++) cin >> T[i] >> X[i] >> queryW[i];
	
	order.resize(m);
	for(int i = 1;i <= m;i++) order[i-1] = i;
	sort(all(order), [&](int a, int b){ return edgeW[a] > edgeW[b]; });
	 
	for(int i = 1;i <= m;i++) history[i].push_back(ii(0, edgeW[i]));
	for(int 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(int 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(int i = 1;i <= Q;i++){
		if(T[i] == QRY) cout << ans[i] << '\n';
	}
}

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27