Submission #1271777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271777		thuhienne	Bridges (APIO19_bridges)	C++17	59 / 100	3095 ms	5880 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

#define size __size__
#define union __union__
#define data __data__

const int can = 350;

int n,m,q;

struct __ {
	int u,v,w,index;
	bool operator < (const __ & other) {
		return w < other.w;
	}
} edge[100009];

bool changed[100009];

int uniq,firsttime[100009];

int root[100009],size[100009];

int getroot(int node) {
	return (node == root[node] ? node : root[node] = getroot(root[node]));
}

void union(int u,int v) {
	u = getroot(u),v = getroot(v);
	if (u != v) root[u] = v,size[v] += size[u];
}

struct data {
	int index,rootbefore,sizebefore,rootafter,sizeafter;
};

int getroot(int node,vector <data> & record) {
	if (node == root[node]) return node;
	int d = getroot(root[node],record);
	record.push_back({node,root[node],size[node],d,size[node]});
	root[node] = d;
	return d;
}
void union(int u,int v,vector <data> & record) {
	u = getroot(u,record);
	v = getroot(v,record);
	if (u == v) return;
	
	record.push_back({u,root[u],size[u],v,size[u]});
	root[u] = v;
	
	record.push_back({v,root[v],size[v],root[v],size[v] + size[u]});
	size[v] += size[u];
	
}

void rollback(vector <data> & record) {
	reverse(record.begin(),record.end());
	for (auto d : record) {
		root[d.index] = d.rootbefore;
		size[d.index] = d.sizebefore;
	}
}


struct query {
	int op,x,y,index;
} ask[100009];

__ bridges[100009];

int answer[100009];

int main() {
	ios_base::sync_with_stdio(0);cin.tie(nullptr);
	//freopen(".inp","r",stdin);
	//freopen(".out","w",stdout);
	cin >> n >> m;
	for (int i = 1;i <= m;i++) {
		cin >> edge[i].u >> edge[i].v >> edge[i].w;
		edge[i].index = i;
	}
	cin >> q;
	for (int ____ = 0;;____++) {
		int l = max(1,____ * can),r = min(q,(____ + 1)*can - 1);
		
		vector <query> contain;
		
		for (int i = l;i <= r;i++) {
			cin >> ask[i].op >> ask[i].x >> ask[i].y;
			ask[i].index = i;
			if (ask[i].op == 1) {
				changed[ask[i].x] = 1;
				bridges[i] = edge[ask[i].x];
			}
			else contain.push_back(ask[i]);
		}
		
		for (int i = 1;i <= n;i++) root[i] = i,size[i] = 1;
		sort(contain.begin(),contain.end(),[] (query a,query b) {
			return a.y > b.y;
		});
		sort(edge + 1,edge + 1 + m);
		int pt = m + 1;
		
		for (auto d : contain) {
			int minimum = d.y,island = d.x;
			while (pt > 1 && edge[pt - 1].w >= minimum) {
				pt--;
				if (!changed[edge[pt].index]) union(edge[pt].u,edge[pt].v);
			}
			
			vector <data> record;
			
			uniq++;
			for (int i = d.index - 1;i >= l;i--) if (ask[i].op == 1) {
				
				__ bridge = bridges[i];
				int w = ask[i].y;
				
				if (firsttime[bridge.index] == uniq) continue;
				firsttime[bridge.index] = uniq;
				
				if (w >= minimum) union(bridge.u,bridge.v,record);
			}
			for (int i = d.index + 1;i <= r;i++) if (ask[i].op == 1) {
				__ bridge = bridges[i];
				if (firsttime[bridge.index] == uniq) continue;
				if (bridge.w >= minimum) union(bridge.u,bridge.v,record);
			}
			
			answer[d.index] = size[getroot(island,record)];
			
			rollback(record);
		}
		
		sort(edge + 1,edge + 1 + m,[] (__ a,__ b) {
			return a.index < b.index;
		});
		
		for (int i = l;i <= r;i++) if (ask[i].op == 1) {
			changed[ask[i].x] = 0;
			edge[ask[i].x].w = ask[i].y;
		}
		
		if (r == q) break;
	}
	for (int i = 1;i <= q;i++) if (ask[i].op == 2) cout << answer[i] << '\n';
}

/*
  Nho doi vai em gay
			  co gai ay ngoi duoi goc pho nen tho ...
*/

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