oj.uz

Submission #375529

# Submission time Handle Problem Language Result Execution time Memory
375529 2021-03-09T13:41:27 Z mode149256 Monthly railway pass (LMIO18_menesinis_bilietas) C++17
100 / 100
 974 ms 97488 KB 
/*input
5 5
3 1 A
3 5 A
4 5 T
2 3 T
2 1 A
*/
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second

vector<int> sz;
vector<int> p;
int findSet(int i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); }
bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
void unionSet(int i, int j) {
	if (isSameSet(i, j)) return;

	int x = findSet(i), y = findSet(j);

	if (sz[x] < sz[y]) swap(x, y);
	p[y] = x;
	sz[x] += sz[y];
}

vector<vector<int>> trauk;

vector<set<int>> newEdges;
vector < pair<int, int>> autob;

vector<bool> visited;
void dfs(int curr) {
	visited[curr] = true;
	// for(int i = 0; i < (int)trauk[curr].size(); i++){
	// 	u = trauk[curr][i];
	for (auto u : trauk[curr]) {
		if (visited[u]) continue;
		unionSet(curr, u);
		dfs(u);
	}
}

int main() {
	int N, M;
	cin >> N >> M;
	sz = vector<int>(N, 1);
	p = vector<int>(N);
	trauk = vector<vector<int>>(N);
	newEdges = vector<set<int>>(N);

	for (int i = 0; i < N; ++i)
		p[i] = i;

	for (int i = 0; i < M; ++i)
	{
		int a, b; char ch;
		cin >> a >> b >> ch; a--; b--;
		if (ch == 'T') {
			trauk[a].emplace_back(b);
			trauk[b].emplace_back(a);
		} else {
			autob.emplace_back(a, b);
		}
	}

	visited = vector<bool>(N, false);
	for (int i = 0; i < N; ++i)
	{
		if (!visited[i])
			dfs(i);
	}

	for (int i = 0; i < (int)autob.size(); ++i)
	{
		pair<int, int> ed = autob[i];
		if (isSameSet(ed.x, ed.y)) continue;

		newEdges[findSet(ed.x)].insert(findSet(ed.y));
		newEdges[findSet(ed.y)].insert(findSet(ed.x));
	}

	set<int> tevai;
	for (int i = 0; i < N; ++i)
	{
		tevai.insert(findSet(i));
	}

	int newN = (int)tevai.size();

	int ats = 0;
	for (auto tevas : tevai) {
		if ((int)newEdges[tevas].size() == newN - 1) {
			ats += sz[tevas];
		}
	}
	cout << ats << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 678 ms 46200 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 142 ms 59372 KB Output is correct
5 Correct 4 ms 1900 KB Output is correct
6 Correct 142 ms 6052 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 59372 KB Output is correct
2 Correct 4 ms 1900 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 7 ms 1260 KB Output is correct
6 Correct 762 ms 44116 KB Output is correct
7 Correct 974 ms 97488 KB Output is correct
8 Correct 20 ms 3852 KB Output is correct
9 Correct 35 ms 5484 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 7 ms 1260 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 4 ms 364 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 7 ms 620 KB Output is correct
11 Correct 5 ms 764 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 11 ms 876 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 2 ms 492 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 2 ms 444 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 3 ms 492 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 4 ms 492 KB Output is correct
5 Correct 7 ms 620 KB Output is correct
6 Correct 5 ms 764 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 11 ms 876 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 444 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 3 ms 492 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 2 ms 492 KB Output is correct
20 Correct 7 ms 1260 KB Output is correct
21 Correct 4 ms 1900 KB Output is correct
22 Correct 20 ms 3852 KB Output is correct
23 Correct 35 ms 5484 KB Output is correct
24 Correct 142 ms 6052 KB Output is correct
25 Correct 23 ms 1028 KB Output is correct
26 Correct 328 ms 9636 KB Output is correct
27 Correct 113 ms 4080 KB Output is correct
28 Correct 306 ms 15456 KB Output is correct
29 Correct 90 ms 3168 KB Output is correct
30 Correct 264 ms 14940 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 4 ms 492 KB Output is correct
5 Correct 7 ms 620 KB Output is correct
6 Correct 5 ms 764 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 11 ms 876 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 444 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 3 ms 492 KB Output is correct
16 Correct 23 ms 1028 KB Output is correct
17 Correct 328 ms 9636 KB Output is correct
18 Correct 113 ms 4080 KB Output is correct
19 Correct 306 ms 15456 KB Output is correct
20 Correct 90 ms 3168 KB Output is correct
21 Correct 264 ms 14940 KB Output is correct
22 Correct 678 ms 46200 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 142 ms 59372 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 2 ms 492 KB Output is correct
28 Correct 7 ms 1260 KB Output is correct
29 Correct 4 ms 1900 KB Output is correct
30 Correct 762 ms 44116 KB Output is correct
31 Correct 974 ms 97488 KB Output is correct
32 Correct 20 ms 3852 KB Output is correct
33 Correct 35 ms 5484 KB Output is correct
34 Correct 142 ms 6052 KB Output is correct
35 Correct 69 ms 6068 KB Output is correct
36 Correct 512 ms 22884 KB Output is correct
37 Correct 342 ms 25620 KB Output is correct