Submission #281721

#	Time	Username	Problem	Language	Result	Execution time	Memory
281721		groeneprof	Bridges (APIO19_bridges)	C++14	14 / 100	692 ms	24032 KiB

bridges

#include <bits/stdc++.h>

#define P(a) do{if(debug) cout<<a<<endl;} while(false)
#define H(a) P(#a<<": "<<a)
#define FR(i,a,b) for(int i = (a); i<(b); i++)
#define F(i,n) FR(i,0,n)
const bool debug = 0;
const int inf = 2e9;

using namespace std;


vector<vector<int> > ts, par, siz;
vector<pair<int,int> > edges;
vector<int> weights;
int n, m, q;

int root(int a,int t){
	if(par[a].back() == a){
		return a;
	}
	if(ts[a].back() > t){
		ts[a].push_back(t);
		par[a].push_back(par[a].back());
		siz[a].push_back(siz[a].back());
	}
	return par[a].back() = root(par[a].back(),t);
}

void merge(int a, int b, int t){
	P("a");	 
	if(rand()%2) swap(a,b);
	int ra = root(a,t), rb = root(b,t);
	if(ra==rb) return;
	if(ts[ra].back()>t){
		ts[ra].push_back(t);
		par[ra].push_back(par[ra].back());
		siz[ra].push_back(siz[ra].back());
	}
	if(ts[rb].back()>t){
		ts[rb].push_back(t);
		par[rb].push_back(par[rb].back());
		siz[rb].push_back(siz[rb].back());
	}
	par[rb].back() = ra;
	siz[ra].back() += siz[rb].back();
}

void generate(){
	siz.resize(n,{1});
	par.resize(n,{0});
	ts.resize(n,{inf});
	F(i,n){
		par[i][0] = i;
	}
	vector<pair<int,pair<int,int> > > sorted(m);
	F(i, m){
		sorted[i] = make_pair(weights[i],edges[i]);
	}
	sort(sorted.rbegin(), sorted.rend());
	for(auto e : sorted){
		merge(e.second.first, e.second.second, e.first);
		/*F(i,n){
			cout<<i<<": ";
			F(j,par[i].size()){
				cout<<"{"<<par[i][j]<<","<<siz[i][j]<<","<<ts[i][j]<<"} ";
			}
			cout<<endl;
		}*/
	}	
	/*F(i,n){
		cout<<i<<": ";
		F(j,par[i].size()){
			cout<<"{"<<par[i][j]<<","<<siz[i][j]<<","<<ts[i][j]<<"} ";
		}
		cout<<endl;
	}*/
}

int root2(int a, int t){
	int i = 0;
	for(int bit = 1<<20; bit>0; bit/=2){
		if(i+bit<ts[a].size() && ts[a][i+bit] >= t){
			i+=bit;
		}
	}
	if(par[a][i] == a) return a;
	return root2(par[a][i],t);
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	edges.resize(m);
	weights.resize(m);
	F(i,m){
		cin>>edges[i].first>>edges[i].second>>weights[i];
		edges[i].first--;
		edges[i].second--;
	}
	generate();

	cin>>q;
	F(i,q){
		int type;
		cin>>type;
		if(type==1){
		
		}
		else{
			int a, t;
			cin>>a>>t;
			a--;
			int ra = root2(a,t);
			H(ra);
			int id = 0;
			for(int bit = 1<<20; bit>0; bit/=2){
				if(id+bit<ts[ra].size() && ts[ra][id+bit] >= t){
					id+=bit;
				}
			}
			cout<<siz[ra][id]<<endl;
		}
	}
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int root2(int, int)':
bridges.cpp:83:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   if(i+bit<ts[a].size() && ts[a][i+bit] >= t){
      |      ~~~~~^~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:120:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     if(id+bit<ts[ra].size() && ts[ra][id+bit] >= t){
      |        ~~~~~~^~~~~~~~~~~~~~

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