Submission #1257171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257171		_rain_	Bridges (APIO19_bridges)	C++20	59 / 100	3093 ms	5696 KiB

bridges

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

const int N = (int)1e5;
const int M = (int)1e5;
const int BLOCKSIZE = (int)317;

struct QUESTION{
	int t;
	int x , y;
	void read(){
		cin >> t >> x >> y;
		return ;
	}
} queri[N + 2];

int n , m , q;
	int x[N + 2] , y[N + 2] , w[N + 2] , tmp[N + 2] ;
	int ans[N + 2] = {};
	bool change[N + 2] = {};

class DSU{
	public:
		vector<int>par , sz;
		vector<pair<int,int>>stack;
		void load_size(int n){
			par.assign(n+2,0) , sz.assign(n+2,1);
			iota(par.begin() , par.end(),0);
		}
		int Find(int u){
			return u == par[u] ? par[u] : Find(par[u]);
		}
		void unite(int u , int v){
			u = Find(u) , v = Find(v);
			if (u==v) {
				stack.push_back({u,v});
				return;
			}
			if (sz[u] < sz[v]) swap(u,v);
			par[v] = u , 
			sz[u] += sz[v];
			stack.push_back({u,v});
			return;
		}
		void roll_back(){
				int u = stack.back().first , v = stack.back().second;
				stack.pop_back();
				if (u==v) return;
				sz[u] -= sz[v];
				par[v] = v ;
			return;
		}
};
DSU dsu;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ;
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin >> n >> m;
		for(int i = 1; i <= m; ++i) cin >> x[i] >> y[i] >> w[i];
		
		cin >> q;
		for(int i = 1; i <= q; ++i) queri[i].read();
		DSU dsu; dsu.load_size(n);
		for(int l = 1 ; l <= q; l += BLOCKSIZE){
			int r = min(l + BLOCKSIZE , q);
			vector<int> edg , upd , ask;
			
			for(int i = 1; i <= m; ++i) change[i] = false;
			for(int i = 1; i <= m; ++i) tmp[i] = w[i];
			
			for(int i = l; i <= r; ++i){
				if (queri[i].t == 1) {
					change[queri[i].x]=true;
					upd.push_back(i);
				}
				else ask.push_back(i);
			}
			for(int i = 1; i <= m; ++i) if (change[i]==false) edg.push_back(i);
			
			sort(edg.begin() , edg.end() , [&](int i , int j){
				return w[i] > w[j];
			});
			sort(ask.begin() , ask.end() , [&](int i , int j){
				return queri[i].y > queri[j].y;
			});
			
			for(int i = 0 , j = 0; i < ask.size() ; ++i){
				int u = queri[ask[i]].x , val = queri[ask[i]].y;
				while (j < edg.size() && w[edg[j]] >= val){
					dsu.unite(x[edg[j]] , y[edg[j]]);
					++j;
				}	
			
				int cnt = 0;
				for(int id : upd) 
					{
						int idx = queri[id].x;
						if (id < ask[i]) w[idx] = queri[id].y;
					}
					for(int id : upd) {
						int idx = queri[id].x;
						if (w[idx] >= val){	
							++cnt;
							dsu.unite(x[idx] , y[idx]);
						}
					}
					for(int id : upd){
						int idx = queri[id].x; 
						w[idx] = tmp[idx];
					}
				
				ans[ask[i]] = dsu.sz[dsu.Find(u)];
				while(cnt) dsu.roll_back() , --cnt;
				
			}
			for(auto& id : upd){
				int idx = queri[id].x;
				w[idx] = queri[id].y;
			}
			while (dsu.stack.size()) dsu.roll_back();
		}
		for(int i = 1; i <= q; ++i) if (queri[i].t==2) cout << ans[i] << '\n';
	return 0;
}

Compilation message (stderr)

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

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