Submission #1237024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237024		i_love_mriti	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	10 / 100	188 ms	5704 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){
	return u == par[u] ? u : 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){
	return u == par2[u] ? u : 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;
	
	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 nn = 0;
  
  for(int i = 1; i <= n; ++i) nn += par[i] == i;

	if(sz[find(1)] == n){
		cout << n << "\n";
		return 0;
	}

	for(int i = 1; i <= n; ++i) sz2[i] = sz[i];

	for(auto it : bus) {
		if(find(it.first) != find(it.second) && find2(it.first) != find2(it.second)){
			++deg[find(it.first)], ++deg[find(it.second)];
			//unite(it.first, it.second);
			unite2(it.first, it.second);
		}
	}

	if(sz2[find(1)] != n - 1){
		cout << "0\n";
		return 0;
	}

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

	cout << ans << "\n";

	return 0;
}

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