Submission #154725

#	Time	Username	Problem	Language	Result	Execution time	Memory
154725		Pro_ktmr	Bridges (APIO19_bridges)	C++14	14 / 100	655 ms	10288 KiB

bridges

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define MP make_pair

//UnionFind
struct UnionFind{
private:
    int N;
    vector<int> par,sz;
public:
    void init(int n){
        N = n;
        par.clear();
        sz.clear();
        for(int i=0; i<N; i++){
            par.push_back(i);
            sz.push_back(1);
        }
    }
    int root(int a){
        if(par[a] == a) return a;
        return par[a] = root(par[a]);
    }
    bool isSame(int a, int b){
        return (root(a) == root(b));
    }
    void unite(int a, int b){
        if(isSame(a, b)) return;
        if(sz[root(a)] < sz[root(b)]){
            sz[root(b)] += sz[root(a)];
			sz[root(a)] = 0;
			par[root(a)] = root(b);
        }
        else{
            swap(a, b);
			sz[root(b)] += sz[root(a)];
			sz[root(a)] = 0;
            par[root(a)] = root(b);
        }
    }
	int size(int a){
		return sz[root(a)];
	}
	void print(){
		for(int i=0; i<N; i++) cout << sz[i] << " ";
		cout << endl;
	}
};

int N,M,Q;
UnionFind uf;
vector<pair<pair<int,int>, pair<int,int>>> all; //cost, type, a, b
vector<pair<int,int>> ans;

int main(){
	cin >> N >> M;
	uf.init(N);
	for(int i=0; i<M; i++){
		int a, b, c;
		cin >> a >> b >> c;
		all.push_back(MP(MP(c, 1),MP(a-1,b-1)));
	}
	cin >> Q;
	for(int i=0; i<Q; i++){
		int t, a, b;
		cin >> t >> a >> b;
		all.push_back(MP(MP(b, -i),MP(a-1,0)));
	}
	sort(all.begin(), all.end());
	reverse(all.begin(), all.end());

	for(int i=0; i<all.size(); i++){
		if(all[i].first.second == 1){
			uf.unite(all[i].second.first, all[i].second.second);
			//cout << "unite: " << all[i].second.first << " " << all[i].second.second << endl;
		}
		else{
			ans.push_back(MP(-all[i].first.second, uf.size(all[i].second.first)));
			//cout << "ans: " << all[i].second.first << " " << uf.size(all[i].second.first) << endl;
			//uf.print();
		}
	}
	sort(ans.begin(), ans.end());
	for(int i=0; i<ans.size(); i++) cout << ans[i].second << endl;
	
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:73:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<all.size(); i++){
               ~^~~~~~~~~~~
bridges.cpp:85:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ans.size(); i++) cout << ans[i].second << endl;
               ~^~~~~~~~~~~

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