Submission #198450

#	Time	Username	Problem	Language	Result	Execution time	Memory
198450		oolimry	Monthly railway pass (LMIO18_menesinis_bilietas)	C++14	16 / 100	558 ms	75180 KiB

menesinis_bilietas

#include <bits/stdc++.h>

using namespace std;
static int p[500005];
int numSets;
int findSet(int u){
	if(p[u] == u) return u;
	else{
		p[u] = findSet(p[u]);
		return p[u];
	}
}

void unionSet(int u, int v){
	u = findSet(u);
	v = findSet(v);
	if(u == v) return;
	p[u] = v;
	numSets--;
}

typedef pair<int,int> ii; 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, m; cin >> n >> m;
	numSets = n;
	unordered_set<int> edges[n];
	for(int i = 0;i < n;i++) p[i] = i;
	vector<ii> bus;
	for(int i = 0;i < m;i++){
		int u, v; char c;
		cin >> u >> v >> c;
		u--; v--;
		if(c == 'T'){
			unionSet(u,v);
		}
		else{
			bus.push_back(ii(u,v));
		}
	}
	
	for(ii e : bus){
		int u = findSet(e.first);
		int v = findSet(e.second);
		edges[u].insert(v);
		edges[v].insert(u);
	}
	
	int ans = 0;
	for(int i = 0;i < n;i++){
		if(numSets - 1 == edges[findSet(i)].size()) ans++;
	}
	
	cout << ans << "\n";
}

Compilation message (stderr)

menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:52:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(numSets - 1 == edges[findSet(i)].size()) ans++;
      ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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