Submission #850885

#	Time	Username	Problem	Language	Result	Execution time	Memory
850885		pakapu	Monthly railway pass (LMIO18_menesinis_bilietas)	C++17	0 / 100	404 ms	44580 KiB

menesinis_bilietas

#include <bits/stdc++.h>

using namespace std;

vector<int> used;
vector<int> cc_size;
vector<int> distribute_used;
vector<int> answer_used;

vector<vector<int>> bus_g;
vector<vector<int>> train_g;

int calculate_cc_size(int u) {
	used[u] = true;
	int curr_size = 1;

	for(auto v : train_g[u]) {
		if(used[v]) {
			continue;
		}

		curr_size += calculate_cc_size(v);
	}

	return curr_size;
}

void distribute_size(int u, int curr_size) {
	distribute_used[u] = true;
	cc_size[u] = curr_size;

	for(auto v : train_g[u]) {
		if(distribute_used[v]) {
			continue;
		}

		distribute_size(v, curr_size);
	}
}

int calculate_cheap_routes(int u) {
	answer_used[u] = true;
	int ans = 0;

	for(auto v : train_g[u]) {
		if(answer_used[v]) {
			continue;
		}

		ans += calculate_cheap_routes(v);
	}

	for(auto v : bus_g[u]) {
		ans += cc_size[v];
	}

	return ans;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n >> m;

	bus_g = vector<vector<int>>(n);
	train_g = vector<vector<int>>(n);

	for(int i = 0; i < m; i++) {
		int from, to;
		char type;
		cin >> from >> to >> type;
		from--;
		to--;

		if(type == 'T') {
			train_g[to].push_back(from);
			train_g[from].push_back(to);
		}
		if(type == 'A') {
			bus_g[to].push_back(from);
			bus_g[from].push_back(to);
		}
	}

	used = vector<int>(n);
	cc_size = vector<int>(n);
	distribute_used = vector<int>(n);
	for(int i = 0; i < n; i++) {
		if(!used[i]) {
			int curr = calculate_cc_size(i);
			distribute_size(i, curr);
			
			/*cout << i << ' ' << curr << '\n';
			for(auto c : cc_size) {
				cout << c << ' ';
			}
			cout << '\n';*/
		}
	}

	// Calculate the number of reachable cities for every node
	int ans = 0;
	answer_used = vector<int>(n);
	vector<int> cheap_cities(n);
	for(int i = 0; i < n; i++) {
		if(!answer_used[i]) {
			cheap_cities[i] = cc_size[i] + calculate_cheap_routes(i);
			if(cheap_cities[i] > cheap_cities[ans]) {
				ans = i;
			}
		}
	}

	cout << ans + 1 << '\n';

	return 0;
}

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