Submission #1130263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130263		heey	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	6 / 100	862 ms	76644 KiB

menesinis_bilietas

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> sz, p, mark;
vector<vector<int>> adj;
void make(int v){
	sz[v] = 1;
	p[v] = v;
}

int dsu(int v){
	if(v == p[v]) return v;
	return p[v] = dsu(p[v]);
}

void join(int a, int b){
	a = dsu(a);
	b = dsu(b);

	if(a != b){
		if(sz[a] < sz[b]) swap(a, b);
		p[b] = a;
		sz[a] += sz[b];
	}
}

void dfs(int v){
	mark[v] = true;

	for(int e : adj[v]){
		if(!mark[e]){
			make(e);
			join(v, e);
			dfs(e);
		}
	}
}

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	
	vector<pair<int,int>> weakedge;
	adj.assign(n, vector<int>());
	sz.assign(n, 0);
	p.assign(n, 0);
	mark.assign(n, false);
	for(int i = 0; i < m; i++){
		int u, v; cin >> u >> v;
		char type; cin >> type;
		u--, v--;
		if(type == 'A') weakedge.emplace_back(u, v);
		else adj[u].emplace_back(v);
	}

	for(int i = 0; i < n; i++){
		if(!mark[i]){
			make(i);
			dfs(i);
		}
	}


	set<int> comp;
	vector<int> dl;
	for(int i = 0; i < n; i++){
		if(!comp.count(dsu(i))){
			comp.insert(dsu(i));
			dl.emplace_back(i);
		}

	}


	set<pair<int,int>> con;
	for(auto edge : weakedge){
		con.insert({dsu(edge.first), dsu(edge.second)});
		con.insert({dsu(edge.second), dsu(edge.first)});
	}

	int res = 0;
	vector<bool> ok(dl.size(), true);
	for(int i = 0; i < (int)dl.size(); i++){
		if(!ok[i]) continue;

		for(int j = 0; j < (int)dl.size(); j++){
			if(i != j){
				if(!con.count({dl[i], dl[j]})){
					ok[i] = false;
					ok[j] = false;
					break;
				}
			}
		}

		if(ok[i]) res += sz[dl[i]];
	}

	cout << res << '\n';

	return 0;
}

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