Submission #1237031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237031		i_love_mriti	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	10 / 100	187 ms	7748 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});
		//cout << u << 
	}

  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], par2[i] = par[i];

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


	//cout << sz2[find(1)] << " " << sz2[find2(1)] << " " << sz2[find2(find(1))] << endl;




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

	//cout << nn - 1 << endl;

	for(int i = 1; i <= n; ++i){

		if(find(i) == i && deg[i] == (nn - 1)){
			ans += sz[find(i)];
			//cout << i << endl;
		}
	}

	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