Submission #375529

#	Time	Username	Problem	Language	Result	Execution time	Memory
375529		mode149256	Monthly railway pass (LMIO18_menesinis_bilietas)	C++17	100 / 100	974 ms	97488 KiB

menesinis_bilietas

/*input
5 5
3 1 A
3 5 A
4 5 T
2 3 T
2 1 A
*/
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second

vector<int> sz;
vector<int> p;
int findSet(int i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); }
bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
void unionSet(int i, int j) {
	if (isSameSet(i, j)) return;

	int x = findSet(i), y = findSet(j);

	if (sz[x] < sz[y]) swap(x, y);
	p[y] = x;
	sz[x] += sz[y];
}

vector<vector<int>> trauk;

vector<set<int>> newEdges;
vector < pair<int, int>> autob;

vector<bool> visited;
void dfs(int curr) {
	visited[curr] = true;
	// for(int i = 0; i < (int)trauk[curr].size(); i++){
	// 	u = trauk[curr][i];
	for (auto u : trauk[curr]) {
		if (visited[u]) continue;
		unionSet(curr, u);
		dfs(u);
	}
}

int main() {
	int N, M;
	cin >> N >> M;
	sz = vector<int>(N, 1);
	p = vector<int>(N);
	trauk = vector<vector<int>>(N);
	newEdges = vector<set<int>>(N);

	for (int i = 0; i < N; ++i)
		p[i] = i;

	for (int i = 0; i < M; ++i)
	{
		int a, b; char ch;
		cin >> a >> b >> ch; a--; b--;
		if (ch == 'T') {
			trauk[a].emplace_back(b);
			trauk[b].emplace_back(a);
		} else {
			autob.emplace_back(a, b);
		}
	}

	visited = vector<bool>(N, false);
	for (int i = 0; i < N; ++i)
	{
		if (!visited[i])
			dfs(i);
	}

	for (int i = 0; i < (int)autob.size(); ++i)
	{
		pair<int, int> ed = autob[i];
		if (isSameSet(ed.x, ed.y)) continue;

		newEdges[findSet(ed.x)].insert(findSet(ed.y));
		newEdges[findSet(ed.y)].insert(findSet(ed.x));
	}

	set<int> tevai;
	for (int i = 0; i < N; ++i)
	{
		tevai.insert(findSet(i));
	}

	int newN = (int)tevai.size();

	int ats = 0;
	for (auto tevas : tevai) {
		if ((int)newEdges[tevas].size() == newN - 1) {
			ats += sz[tevas];
		}
	}
	cout << ats << '\n';
}

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