Submission #634677

#	Time	Username	Problem	Language	Result	Execution time	Memory
634677		mrkhan2000	Monthly railway pass (LMIO18_menesinis_bilietas)	C++17	100 / 100	542 ms	65284 KiB

menesinis_bilietas

#include <bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;

class union_find {
private:
	int N;
	int components;
	vector<int> sz, pa;
public:
	union_find(int N) : N(N), components(N), sz(vector<int>(N,1)), pa(vector<int>(N)) {
		iota(pa.begin(), pa.end(), 0);
	}
	void unite(int u, int v) {
		if(u >= N || v >= N) return;
		u = find(u);
		v = find(v);
		if(u == v) return;
		if(sz[u] < sz[v]) swap(u, v);
		sz[u] += sz[v];
		pa[v] = u;
		--components;
	}
	int find(int u) {
		if(u >= N) return -1;
		while(pa[u]^u) u = pa[u];
		return u;
	}
	int _size(int u) {
		return sz[find(u)];
	}
	int getComponentsCount() {
		return components;
	}
};


void solve() {
	int N, E; cin >> N >> E;
	union_find UF(N);
	vector<vector<int>> bcns;
	bcns.reserve(E);
	for(int i = 0; i < E; i++) {
		int U, V; cin >> U >> V;
		char T; cin >> T;
		--U, --V;
		if(T == 'T') UF.unite(U, V);
		else bcns.push_back({U,V});
	}
	set<int> rep;
	for(int i = 0; i < N; i++) {
		rep.insert(UF.find(i));
	}
	vector<int> deg(N);
	set<pair<int,int>> done;
	for(auto &cns : bcns) if(
		UF.find(cns[0])^UF.find(cns[1]) && 
		done.find({UF.find(cns[0]), UF.find(cns[1])}) == done.end()
	) {
		deg[UF.find(cns[0])]++;
		deg[UF.find(cns[1])]++;
		done.insert({UF.find(cns[0]), UF.find(cns[1])});
	}
	set<int> work;
	for(auto city : rep) {
		if(deg[city] == UF.getComponentsCount() - 1) {
			work.insert(city);
		}
	}
	int ans = 0;
	for(int i = 0; i < N; i++) {
		if(work.find(UF.find(i)) != work.end()) {
			++ans;
		}
	}
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int test_cases = 1;
	// cin >> test_cases;
	for(int test_case = 1; test_case <= test_cases; test_case++) {
		// cout << "Case #" << test_case << ": ";
		solve();
	}
	return 0;
}

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