oj.uz

Submission #826380

# Submission time Handle Problem Language Result Execution time Memory
826380 2023-08-15T13:48:57 Z OAleksa Monthly railway pass (LMIO18_menesinis_bilietas) C++14
16 / 100
 509 ms 74568 KB 
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std; 
#define int long long
const int maxn = 5e5 + 69;
vector<int> g[maxn];
vector<int> p(maxn), sz(maxn);
vector<int> deg(maxn);
int find_set(int v) {
	if(p[v] == v)
		return v;
	return p[v] = find_set(p[v]);
}

void unite(int a, int b) {
	a = find_set(a);
	b = find_set(b);
	if(a != b) {
		if(sz[a] < sz[b])	
			swap(a, b);
		p[b] = a;
		sz[a] += sz[b];
	}
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tt = 1;
	//cin >> tt;
	while(tt--) {
		int n, m;
		cin >> n >> m;
		vector<pair<int, int>> edges;
		for(int i = 1;i <= n;i++) {
			p[i] = i;
			sz[i] = 1;
		}
		for(int i = 0;i < m;i++) {
			int a, b;
			char c;
			cin >> a >> b >> c;
			if(c == 'T') 
				unite(a, b);
			else 
				edges.push_back({a, b});
		}
		set<int> kurac;
		for(int i = 1;i <= n;i++) 
			kurac.insert(find_set(i));
		int c = kurac.size();
		int ans = 0;
		set<pair<int, int>> bio;
		for(auto x : edges) {
			int a = find_set(x.f);
			int b = find_set(x.s);
			if(a > b)
				swap(a, b);
			if(bio.count({a, b}))
				continue;
			else {
				bio.insert({a, b});
				deg[a]++;
				deg[b]++;
			}
		}
		for(auto x : kurac)
			ans += (deg[x] >= c - 1 ? sz[x] : 0);
		if(c == 1)
			ans = n;
		cout << ans;
	}
   return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 23764 KB Output is correct
2 Correct 17 ms 23764 KB Output is correct
3 Correct 10 ms 23764 KB Output is correct
4 Correct 97 ms 45812 KB Output is correct
5 Correct 12 ms 24404 KB Output is correct
6 Correct 32 ms 23764 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 45812 KB Output is correct
2 Correct 12 ms 24404 KB Output is correct
3 Correct 9 ms 23724 KB Output is correct
4 Correct 9 ms 23892 KB Output is correct
5 Correct 13 ms 24420 KB Output is correct
6 Correct 287 ms 51752 KB Output is correct
7 Correct 509 ms 74568 KB Output is correct
8 Correct 17 ms 25688 KB Output is correct
9 Correct 23 ms 26692 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23764 KB Output is correct
2 Correct 10 ms 23764 KB Output is correct
3 Correct 9 ms 23724 KB Output is correct
4 Correct 9 ms 23892 KB Output is correct
5 Correct 13 ms 24420 KB Output is correct
6 Correct 9 ms 23764 KB Output is correct
7 Correct 9 ms 23764 KB Output is correct
8 Correct 10 ms 23892 KB Output is correct
9 Correct 10 ms 23992 KB Output is correct
10 Correct 12 ms 24148 KB Output is correct
11 Correct 11 ms 24020 KB Output is correct
12 Correct 10 ms 23764 KB Output is correct
13 Correct 9 ms 23764 KB Output is correct
14 Correct 14 ms 24148 KB Output is correct
15 Correct 10 ms 23764 KB Output is correct
16 Correct 11 ms 23784 KB Output is correct
17 Incorrect 12 ms 23808 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23764 KB Output is correct
2 Correct 9 ms 23764 KB Output is correct
3 Correct 10 ms 23892 KB Output is correct
4 Correct 10 ms 23992 KB Output is correct
5 Correct 12 ms 24148 KB Output is correct
6 Correct 11 ms 24020 KB Output is correct
7 Correct 10 ms 23764 KB Output is correct
8 Correct 9 ms 23764 KB Output is correct
9 Correct 14 ms 24148 KB Output is correct
10 Correct 10 ms 23764 KB Output is correct
11 Correct 11 ms 23784 KB Output is correct
12 Incorrect 12 ms 23808 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23764 KB Output is correct
2 Correct 9 ms 23764 KB Output is correct
3 Correct 10 ms 23892 KB Output is correct
4 Correct 10 ms 23992 KB Output is correct
5 Correct 12 ms 24148 KB Output is correct
6 Correct 11 ms 24020 KB Output is correct
7 Correct 10 ms 23764 KB Output is correct
8 Correct 9 ms 23764 KB Output is correct
9 Correct 14 ms 24148 KB Output is correct
10 Correct 10 ms 23764 KB Output is correct
11 Correct 11 ms 23784 KB Output is correct
12 Incorrect 12 ms 23808 KB Output isn't correct
13 Halted 0 ms 0 KB -