oj.uz

Submission #850907

# Submission time Handle Problem Language Result Execution time Memory
850907 2023-09-17T18:42:51 Z pakapu Monthly railway pass (LMIO18_menesinis_bilietas) C++17
16 / 100
 354 ms 62148 KB 
#include <bits/stdc++.h>

using namespace std;

set<int> used_cc;

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

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

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

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

		curr_size += calculate_cc_size(v, leader);
	}

	return 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]) {
		if(used_cc.count(cc_leader[v])) {
			continue;
		}
		used_cc.insert(cc_leader[v]);
		ans += cc_size[cc_leader[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);
		}
	}

	cc_leader = vector<int>(n, -1);

	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, i);
			assert(cc_leader[i] != -1);
			cc_size[cc_leader[i]] = curr;
		}
	}

	// 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]) {
			used_cc.clear();
			assert(cc_leader[i] != -1);
			cheap_cities[cc_leader[i]] = cc_size[cc_leader[i]] + calculate_cheap_routes(i);
			assert(cheap_cities[cc_leader[i]] <= n);
		}
	}

	for(int i = 0; i < n; i++) {
		assert(cc_leader[i] != -1);
		if(cheap_cities[cc_leader[i]] == n) {
			ans++;
		}
	}
	cout << ans << '\n';

	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 45644 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 17 ms 33572 KB Output is correct
5 Correct 1 ms 1368 KB Output is correct
6 Correct 31 ms 3932 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33572 KB Output is correct
2 Correct 1 ms 1368 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 3 ms 856 KB Output is correct
6 Correct 156 ms 9868 KB Output is correct
7 Correct 354 ms 62148 KB Output is correct
8 Correct 9 ms 2648 KB Output is correct
9 Correct 11 ms 2648 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 3 ms 856 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Runtime error 2 ms 856 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Runtime error 2 ms 856 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Runtime error 2 ms 856 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -