Submission #795920

#	Time	Username	Problem	Language	Result	Execution time	Memory
795920		vjudge1	Monthly railway pass (LMIO18_menesinis_bilietas)	C++17	100 / 100	654 ms	88652 KiB

menesinis_bilietas

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

#define mp make_pair
#define pb push_back
#define pii pair<int, int>

const int maxN = 1e6 + 10;

int n, m;
vector<int> v[maxN];
int cmp[maxN];
int a[maxN], b[maxN];
int other[maxN], tot[maxN];
int cur;
map<pii, bool> mapa;

void dfs(int x, int comp) {
	cmp[x] = comp;
	tot[comp]++;

	for (int i: v[x]) {
		if (!cmp[i]) {
			dfs(i, comp);
		}
	}
}

int main() {

	cin >> n >> m;

	for (int i = 1; i<= m; i++) {
		int x, y;
		char ch;
		scanf("%d %d %c",&x,&y, &ch);
		if (ch == 'T') {
			v[x].pb(y);
			v[y].pb(x);
		} else {
			a[++cur] = x;
			b[cur] = y;
		}
	}


	int cmpCount = 0;
	for (int i = 1; i <= n; i++) {
		if (!cmp[i]) {
			dfs(i, ++cmpCount);
		}
	}

	if (cmpCount == 1) {
		cout << n << endl;
		return 0;
	}

	for (int i = 1; i <= cur; i++) {
		if (cmp[a[i]] != cmp[b[i]]) {
			int x = cmp[a[i]];
			int y = cmp[b[i]];
			pii edge = mp(x, y);
			if (mapa[edge] == false) {
				mapa[edge] = true;
				other[x]++;
				mapa[mp(y, x)] = true;
				other[y]++;
			}
		}
	}

	int ans = 0;

	for (int i = 1; i<= cmpCount; i++) {
		if (other[i] == cmpCount - 1) ans+= tot[i];
	}

	cout << ans << endl;
}

Compilation message (stderr)

menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   scanf("%d %d %c",&x,&y, &ch);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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