Submission #1240437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240437		rayan_bd	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	100 / 100	426 ms	44732 KiB

menesinis_bilietas

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

const int mxN = 5e5 + 100;

int par[mxN], sz[mxN], deg[mxN], par2[mxN], sz2[mxN];
set<pair<int, int>> bus;


int find(int u){
	if(u == par[u]) return u;
	return par[u] = find(par[u]);
}

void unite(int u, int v){
	u = find(u), v = find(v);
	if(u == v) return;
	par[u] = v, sz[v] += sz[u];
}

int find2(int u){
	if(u == par2[u]) return u;
	return par2[u] = find2(par2[u]);
}

void unite2(int u, int v){
	u = find2(u), v = find2(v);
	if(u == v) return;
	par2[u] = v, sz2[v] += sz2[u];
}

int main(){
	int n, m, u, v, ans = 0;
	cin >> n >> m;
	char ch;
	for(int i = 1; i <= n; ++i) sz[i] = 1, par[i] = i, par2[i] = i;
	
	for(int i = 0; i < m; ++i){
		cin >> u >> v >> ch;
		if(u > v) swap(u, v);
		if(ch == 'T') unite(u, v);
		else bus.insert({u, v});
	}

	int rem = 0;

	for(int i = 1; i <= n; ++i) rem += par[i] == i;

	set<pair<int,int>> nbus;

	for(auto it : bus){
		it.first = find(it.first);
		it.second = find(it.second);
		if(it.first == it.second) continue;
		nbus.insert({min(it.first, it.second), max(it.first, it.second)});
	}

	for(auto it : nbus){
		//cout << it.first << " " << it.second << endl;
		++deg[it.first], ++deg[it.second];
	}

	for(int i = 1; i <= n; ++i){
		if(find(i) == i && deg[i] == rem - 1) ans += sz[find(i)];
	}

	cout << ans << endl;

	return 0;
}

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