Submission #920858

#	Time	Username	Problem	Language	Result	Execution time	Memory
920858		yhkhoo	Monthly railway pass (LMIO18_menesinis_bilietas)	C++17	100 / 100	536 ms	110560 KiB

menesinis_bilietas

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

typedef pair<int, int> pii;

vector<int> p;

int get_parent(int x){
	if(p[x] == x) return x;
	p[x] = get_parent(p[x]);
	return p[x];
}

void union_set(int u, int v){
	u = get_parent(u);
	v = get_parent(v);
	if(u==v) return;
	p[u] = v;
}

int main(){
	cin.tie(0); ios_base::sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	p.clear();
	p.reserve(n);
	for(int i=0; i<n; i++){
		p.push_back(i);
	}
	vector<pii> bus;
	bus.reserve(m);
	for(int i=0; i<m; i++){
		int a, b;
		char t;
		cin >> a >> b >> t;
		a--; b--;
		if(t=='T'){
			union_set(a, b);
		}
		else{
			bus.emplace_back(a, b);
		}
	}
	vector<int> ss(n, 0);
	for(int i=0; i<n; i++){
		ss[get_parent(i)]++;
	}
	int nc=0;
	for(int i=0; i<n; i++){
		if(ss[i] != 0){
			nc++;
		}
	}
	vector<unordered_set<int>> sadj(n);
	for(auto i: bus){
		int a = get_parent(i.first);
		int b = get_parent(i.second);
		if(a==b) continue;
		sadj[a].insert(b);
		sadj[b].insert(a);
	}
	int ans=0;
	for(int i=0; i<n; i++){
		if(sadj[i].size() == nc-1){
			ans += ss[i];
		}
	}
	cout << ans;
	return 0;
}

Compilation message (stderr)

menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:64:21: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |   if(sadj[i].size() == nc-1){
      |      ~~~~~~~~~~~~~~~^~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 6 / 6
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35
• Subtask 5: 19 / 19