Submission #1176689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176689		mertbbm	Bridges (APIO19_bridges)	C++20	59 / 100	3092 ms	14072 KiB

bridges

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

//#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

struct DSU{
	vector<int>e;
	vector<array<int,4>>stk;
	void init(int n){
		e=vector<int>(n,-1);
	}
	
	int get(int x){
		return e[x]<0?x:get(e[x]);
	}
	
	bool unite(int x, int y){
		x=get(x); y=get(y);
		if(x==y) return 0;
		if(e[x]>e[y]) swap(x,y);
		stk.push_back({x,y,e[x],e[y]});
		e[x]+=e[y];
		e[y]=x;
		return 1;
	}
	
	void rollback(){
		array<int,4>hold=stk.back();
		stk.pop_back();
		//x y e[x] e[y]
		e[hold[0]]=hold[2];
		e[hold[1]]=hold[3];
	}
};

const int blk=400;

bool cmp(const array<int,3>&a, const array<int,3>&b){
	return a[1]>b[1];
}

void solve(){
	int n,m;
	cin >> n >> m;
	array<int,3>arr[m];
	set<pair<pii,pii>,greater<>>edge;
	pii storage[m];
	for(int x=0;x<m;x++){
		cin >> arr[x][0] >> arr[x][1] >> arr[x][2];
		edge.insert({{arr[x][2],arr[x][0]},{arr[x][1],x}});
		storage[x]={arr[x][0],arr[x][1]};
	}
	
	int q;
	cin >> q;
	
	vector<array<int,3>>que[500];
	vector<array<int,3>>upd[500];
	int temp,temp2,temp3;
	for(int x=0;x<q;x++){
		cin >> temp >> temp2 >> temp3;
		if(temp==1){
			temp2--;
			upd[x/blk].push_back({temp2,temp3,x});
		}
		else{
			que[x/blk].push_back({temp2,temp3,x});
		}
	}

	vector<pii>ans;
	for(int x=0;x<(q/blk)+1;x++){
		//rebuild structure
		bitset<100005>bs;
		vector<int>notake;
		for(auto it:upd[x]){
			int index=it[0];
			bs[index]=true;
			notake.push_back(index);
		}
		
		DSU dsu;
		dsu.init(n+5);
		auto ptr=edge.begin();
		
		sort(que[x].begin(),que[x].end(),cmp);
		for(auto it:que[x]){
			while(ptr!=edge.end()&&ptr->first.first>=it[1]){
				if(!bs[ptr->second.second]){
					dsu.unite(ptr->first.second,ptr->second.first);
				}
				ptr++;
			}
			int counter=0;
			vector<pii>undo;
			for(auto brute:upd[x]){
				if(brute[2]<it[2]){
					undo.push_back({brute[0],arr[brute[0]][2]});
					arr[brute[0]][2]=brute[1];
				}
			}
			for(auto brute:notake){
				if(arr[brute][2]>=it[1]){
					counter+=dsu.unite(arr[brute][1],arr[brute][0]);
				}
			}
			ans.push_back({it[2],-dsu.e[dsu.get(it[0])]});
			for(int y=0;y<counter;y++) dsu.rollback();
			while(!undo.empty()){
				arr[undo.back().first][2]=undo.back().second;
				undo.pop_back();
			}
		}
		
		for(auto it:upd[x]){
			int index=it[0];
			pair<pii,pii>hold={{arr[index][2],arr[index][0]},{arr[index][1],index}};
			edge.erase(hold);
			arr[index][2]=it[1];
			hold.first.first=it[1];
			edge.insert(hold);
		}
	}
	
	sort(ans.begin(),ans.end());
	for(auto it:ans) cout << it.second << "\n";
}
																   
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

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