제출 #1139320

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139320		dariustgame	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	16 / 100	496 ms	78376 KiB

menesinis_bilietas

#include <iostream>
#include <set>
#include <vector>

using namespace std;

int n, m;
vector<int> graf[500005];
vector<pair<int, int>> bus;
int dad[500005];
int sizeC[500005];
set<int> compCon[500005];

int getDad(int nod)
{
	if (dad[nod] == 0)
	{
		return nod;
	}
	else
	{
		return dad[nod] = getDad(dad[nod]);
	}
}

void uni(int nod1, int nod2)
{
	int dad1 = getDad(nod1);
	int dad2 = getDad(nod2);
	if (dad1 != dad2)
	{
		dad[dad1] = dad2;
		sizeC[dad2] = sizeC[dad1] + sizeC[dad2];
	}
}

int main()
{
	cin >> n >> m;
	int x, y;
	char z;
	for (int i = 0; i <= n; i++)
	{
		sizeC[i] = 1;
	}
	for (int i = 0; i < m; i++)
	{
		cin >> x >> y >> z;
		if (z == 'T')
		{
			uni(x, y);
		}
		else
		{
			bus.push_back({ x, y });
		}
	}
	int nrCompCon = 0;
	for (int i = 1; i <= n; i++)
	{
		if (dad[i] == 0)
		{
			nrCompCon++;
		}
	}
	for (int i = 0; i < bus.size(); i++)
	{
		compCon[getDad(bus[i].first)].insert(getDad(bus[i].second));
		compCon[getDad(bus[i].second)].insert(getDad(bus[i].first));
	}
	int total = 0;
	for (int i = 1; i <= n; i++)
	{
		if (dad[i] == 0 && compCon[i].size() == nrCompCon -1)
		{
			total += sizeC[i];
		}
	}
	cout << total;
}

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