Submission #1165714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165714		tamyte	Monthly railway pass (LMIO18_menesinis_bilietas)	C++17	100 / 100	649 ms	76564 KiB

menesinis_bilietas

#include <bits/stdc++.h>



using namespace std;

struct DSU {
	vector<int> e;
	DSU(int n) {
		e = vector<int>(n, -1);
	}
	int get(int x) {
		return e[x] < 0 ? x : e[x] = get(e[x]);
	}
	void unite(int x, int y) {
		x = get(x);
		y = get(y);
		if (x == y) return;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y];
		e[y] = x;
	}
	int size(int x) {
		return -e[get(x)];
	}
	
};

int main() {
	int N, M;
	cin >> N >> M;
	vector<vector<int>> F(N + 1), C(N + 1);
	for (int i = 0; i < M; ++i) {
		int a, b;
		char c;
		cin >> a >> b >> c;
		if (c == 'A') {
			C[a].push_back(b);
			C[b].push_back(a);
		} else {
			F[a].push_back(b);
			F[b].push_back(a);
		}
	}
	DSU dsu(N + 1);
	for (int i = 1; i <= N; ++i) {
		for (auto& u : F[i]) {
			dsu.unite(u, i);
		}
	}
	int res = 0;
	vector<vector<int>> seg(N + 1);
	for (int i = 1; i <= N; ++i){
		seg[dsu.get(i)].push_back(i);
	}
	for (int i = 1; i <= N; ++i) {
		if (seg[i].size() == 0) continue;
		set<int> st;
		int now = 0;
		st.insert(i);
		for (auto& v : seg[i]) {
			for (auto& u : C[v]) {
				st.insert(dsu.get(u));
			}
		}
		for (auto& u : st) {
			now += dsu.size(u);
		}
		if (now == N) {
			res += seg[i].size();
		}
	}
	cout << res << endl;
}

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