Submission #398294

#	Time	Username	Problem	Language	Result	Execution time	Memory
398294		oolimry	Bridges (APIO19_bridges)	C++17	46 / 100	3093 ms	18752 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];

inline void reset(){
	for(int i = 1;i <= n;i++) p[i] = i, sz[i] = 1;
}

inline int findSet(int x){
	int u = x;
	while(u != p[u]) u = p[u];
	return p[x] = u;
}

inline void unionSet(int u, int v){
	u = findSet(u), v = findSet(v);
	if(u == v) return;
	if((u^v)&1) swap(u,v);
	p[u] = v;
	sz[v] += sz[u];
}


vector<int> order;
int ptr = 1;
inline void catchup(int limit){
	for(;ptr <= limit;ptr++){
		if(T[ptr] == UPD){
			edgeW[X[ptr]] = queryW[ptr];
		}
	}
	sort(all(order), [&](int a, int b){ return edgeW[a] > edgeW[b]; });
}

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;
}

bool changed[100005];
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;
		//show(qid);
		
		while(it != order.end()){
			if(edgeW[*it] < w) break;
			else{
				int e = *it;
				if(not changed[e]){
					//show(e);
					//show2(U[e], V[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);
			}
			//show2(u,v);
		}
		
		int source = findSet(X[qid]);
		special.push_back(source);
		
		//show(source);
		int res = dfs(source);
		ans[qid] = res;
		//show(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 B = 800;

int main(){
	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];
	
	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;
	
	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]));
	}
	
	for(int i = 1;i <= Q;i += B){
		solve(i, min(i+B-1,Q));
	}
	
	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: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27