Submission #920906

#	Time	Username	Problem	Language	Result	Execution time	Memory
920906		theghostking1	Monthly railway pass (LMIO18_menesinis_bilietas)	C++17	100 / 100	677 ms	86968 KiB

menesinis_bilietas

#include <bits/stdc++.h>
using namespace std;

struct DSU{
	vector<int> parent,sz;
	DSU(int n){
		parent.resize(n);
		for (int i = 0; i<n; i++){
			parent[i] = i;
		}
		sz.resize(n,1);
	}
	int find(int x){
		if (x != parent[x]){
			return parent[x] = find(parent[x]);	
		}
		return x;
	}
	bool merge(int a, int b){
		a = find(a);
		b = find(b);
		if (a == b) return false;
		if (sz[a] < sz[b]) swap(a,b);
		parent[b] = a;
		sz[a] += sz[b];
		return true;
	}
	int getsz(int x){
		x = find(x);
		return sz[x];
	}
};

vector<set<int>> adj;

int main(){
	int n,m;
	cin >> n >> m;
	adj.resize(n);
	DSU dsu = DSU(n);
	DSU ck = DSU(n);
	vector<array<int,2>> all;
	for (int i = 0; i<m; i++){
		int a,b;
		char c;
		cin >> a >> b >> c;
		a--;b--;
		if (c == 'T'){
			dsu.merge(a,b);
		}
		ck.merge(a,b);
		if (c == 'T') continue;
		all.push_back({a,b});
	}
	if (ck.getsz(0) != n){
		cout << 0 << '\n';
	}
	else{
		set<int> tot;
		for (int i = 0; i<n; i++){
			tot.insert(dsu.find(i));
		}
		int num = tot.size();
		if (num <= 2){
			cout << n << '\n';
			return 0;
		}
		for (int i = 0; i<(int)all.size(); i++){
			int one = all[i][0];
			int two = all[i][1];
			one = dsu.find(one);
			two = dsu.find(two);
			if (one == two) continue;
			adj[one].insert(two);
			adj[two].insert(one);
		}
		int cnt = 0;
		for (int i = 0; i<n; i++){
			if (adj[i].size() == num-1){
				cnt += dsu.getsz(i);
			}
		}
		cout << cnt << '\n';
	}
	return 0;
}

Compilation message (stderr)

menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:79:22: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |    if (adj[i].size() == num-1){
      |        ~~~~~~~~~~~~~~^~~~~~~~

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