Submission #1176686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176686		mertbbm	Bridges (APIO19_bridges)	C++20	73 / 100	3092 ms	21872 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){
		//show2(unite,x,unite,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=500;

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});
		}
	}
	
	//show(done,1);
	
	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]){
				//show(loop,2);
				//cout << ptr->first.first << " " << ptr->first.second << " " << ptr->second.first << " " << ptr->second.second << " ptr" << endl;
				if(!bs[ptr->second.second]){
					//show2(a,ptr->first.second,b,ptr->second.first);
					dsu.unite(ptr->first.second,ptr->second.first);
				}
				ptr++;
				//show(loop,1);
			}
			//cout << it[0] << " " << it[1] << " " << it[2] << " query" << endl;
			int counter=0;
			//show(check,2);
			vector<pii>undo;
			for(auto brute:upd[x]){
				//cout << brute[0] << " " << brute[1] << 
				if(brute[2]<it[2]){
					undo.push_back({brute[0],arr[brute[0]][2]});
					arr[brute[0]][2]=brute[1];
				}
			}
			for(auto brute:notake){
				//cout << arr[brute][2] << " " << brute << " check\n"; 
				if(arr[brute][2]>=it[1]){
					//cout << arr[brute][1] << " " << arr[brute][0] << " extra" << endl;
					counter+=dsu.unite(arr[brute][1],arr[brute][0]);
				}
			}
			//show(check,1);
			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);
		}
		
		//for(auto hmm:edge){
			//cout << hmm.first.first <<" " << hmm.first.second << " " << hmm.second.first << " " <<hmm.second.second << "\n";
		//}
		//cout << " edge\n\n";
	}
	
	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: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 0 / 27