Submission #166598

#	Time	Username	Problem	Language	Result	Execution time	Memory
166598		Feeder	Bridges (APIO19_bridges)	C++11	100 / 100	2978 ms	9948 KiB

bridges

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

int par[50001], sz[50001], rnk[50001];

int findp(int x){
	return x == par[x] ? x : findp(par[x]);
}

void merge(int x, int y){
	x = findp(x), y = findp(y);
	if(x == y) return;
	if(rnk[x] < rnk[y]) swap(x, y);
	par[y] = x;
	if(rnk[x] == rnk[y]) rnk[x]++;
	sz[x] += sz[y];
}

int edgea[100001], edgeb[100001], ans[100001];
vector<tuple<int, int> > edgelist;
vector<tuple<int, int, int> > uvec; // query, bridge, weight
vector<tuple<int, int, int> > qvec; // weight, query, island
int cbridges[100001];

void findans(int qnum){
	vector<tuple<int, int, int> > st;
	vector<int> vec;
	int qw, qi, qq;
	tie(qw, qq, qi) = qvec[qnum];
	int aa, bb, ww;
	for(int i=int(uvec.size())-1; i>=0; i--){
		if(get<0>(uvec[i]) > qq) continue;
		int bnum = get<1>(uvec[i]);
		ww = get<2>(uvec[i]);
		if(cbridges[bnum] == 2) continue;
		cbridges[bnum] = 2;
		vec.push_back(bnum);
		if(ww < qw) continue;
		aa = edgea[bnum], bb = edgeb[bnum];
		aa = findp(aa), bb = findp(bb);
		if(aa == bb) continue;
		if(rnk[aa] < rnk[bb]) swap(aa, bb);
		if(rnk[aa] == rnk[bb]){
			st.emplace_back(aa, bb, sz[aa]);
			rnk[aa]++;
		}
		else st.emplace_back(aa, bb, -sz[aa]);
		par[bb] = aa;
		sz[aa] += sz[bb];
	}
	for(auto i:vec) cbridges[i] = 1;
	ans[qq] = sz[findp(qi)];
	for(int i=int(st.size())-1; i>=0; i--){
		tie(aa, bb, ww) = st[i];
		if(ww > 0) rnk[aa]--;
		else ww = -ww;
		par[bb] = bb;
		sz[aa] = ww;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, a, b, w, q, qcnt, warr[100001], rt = 200;
	cin >> n >> m;
	for(int i=1; i<=m; i++){
		cin >> edgea[i] >> edgeb[i] >> warr[i];
		edgelist.emplace_back(-warr[i], i);
	}
	sort(edgelist.begin(), edgelist.end());
	
	cin >> q;
	int tarr[100001], aarr[100001], barr[100001], curq = 0;
	for(int i=0; i<q; i++) cin >> tarr[i] >> aarr[i] >> barr[i];
	for(int i=0; i<q; i++){
		a = aarr[i], b = barr[i];
		if(tarr[i] == 1){
			uvec.emplace_back(i, a, b);
			if(!cbridges[a]){
				cbridges[a] = 1;
				uvec.emplace_back(-1, a, warr[a]);
			}
			curq += 1;
		}
		else qvec.emplace_back(b, i, a);
		if(curq != rt - 1 && i != q - 1) continue;
		curq = 0;
		
		qcnt = int(qvec.size()) - 1;
		sort(qvec.begin(), qvec.end());
		sort(uvec.begin(), uvec.end());
		for(int j=1; j<=n; j++) par[j] = j;
		fill(sz + 1, sz + n + 1, 1);
		fill(rnk + 1, rnk + n + 1, 0);
		for(auto it:edgelist){
			tie(w, a) = it;
			w = -w;
			while(qcnt >= 0 && get<0>(qvec[qcnt]) > w) findans(qcnt--);
			if(cbridges[a]) continue;
			merge(edgea[a], edgeb[a]);
		}
		while(qcnt >= 0) findans(qcnt--);
		vector<tuple<int, int> > vec;
		vector<tuple<int, int> > newvec(edgelist);
		edgelist.clear();
		for(int j=int(uvec.size())-1; j>=0; j--){
			tie(qcnt, b, w) = uvec[j];
			if(qcnt < 0) break;
			if(cbridges[b] == 2) continue;
			vec.emplace_back(-w, b);
			warr[b] = w;
			cbridges[b] = 2;
		}
		sort(vec.begin(), vec.end());
		int cnt1 = 0, cnt2 = 0;
		while(cnt1 < newvec.size() || cnt2 < vec.size()){
			if(cnt1 == newvec.size()) edgelist.push_back(vec[cnt2++]);
			else if(cnt2 == vec.size()){
				if(cbridges[get<1>(newvec[cnt1])] != 2) edgelist.push_back(newvec[cnt1++]);
				else cnt1++;
			}
			else if(get<0>(newvec[cnt1]) < get<0>(vec[cnt2])){
				if(cbridges[get<1>(newvec[cnt1])] != 2) edgelist.push_back(newvec[cnt1++]);
				else cnt1++;
			}
			else edgelist.push_back(vec[cnt2++]);
		}
		
		for(int j=int(uvec.size())-1; j>=0; j--){
			tie(qcnt, b, w) = uvec[j];
			if(qcnt < 0) break;
			if(cbridges[b] == 2) cbridges[b] = 0;
		}
		uvec.clear();
		qvec.clear();
	}
	for(int i=0; i<q; i++){
		if(ans[i]) cout << ans[i] << '\n';
	}
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:117:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(cnt1 < newvec.size() || cnt2 < vec.size()){
         ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:117:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(cnt1 < newvec.size() || cnt2 < vec.size()){
                                 ~~~~~^~~~~~~~~~~~
bridges.cpp:118:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(cnt1 == newvec.size()) edgelist.push_back(vec[cnt2++]);
       ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:119:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    else if(cnt2 == vec.size()){
            ~~~~~^~~~~~~~~~~~~

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