oj.uz

Submission #826379

# Submission time Handle Problem Language Result Execution time Memory
826379 2023-08-15T13:46:43 Z OAleksa Monthly railway pass (LMIO18_menesinis_bilietas) C++14
16 / 100
 482 ms 78360 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), vis(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(int i = 1;i <= n;i++) {
			if(deg[i] >= c - 1)
				ans += sz[i];
		}
		if(c == 1)
			ans = n;
		cout << ans;
	}
   return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 27732 KB Output is correct
2 Correct 10 ms 27604 KB Output is correct
3 Correct 10 ms 27732 KB Output is correct
4 Correct 104 ms 49688 KB Output is correct
5 Correct 14 ms 28296 KB Output is correct
6 Correct 35 ms 27716 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 49688 KB Output is correct
2 Correct 14 ms 28296 KB Output is correct
3 Correct 11 ms 27732 KB Output is correct
4 Correct 10 ms 27732 KB Output is correct
5 Correct 14 ms 28300 KB Output is correct
6 Correct 279 ms 55660 KB Output is correct
7 Correct 482 ms 78360 KB Output is correct
8 Correct 21 ms 29548 KB Output is correct
9 Correct 25 ms 30648 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 27604 KB Output is correct
2 Correct 10 ms 27732 KB Output is correct
3 Correct 11 ms 27732 KB Output is correct
4 Correct 10 ms 27732 KB Output is correct
5 Correct 14 ms 28300 KB Output is correct
6 Correct 11 ms 27604 KB Output is correct
7 Correct 10 ms 27732 KB Output is correct
8 Correct 11 ms 27808 KB Output is correct
9 Correct 15 ms 27860 KB Output is correct
10 Correct 14 ms 28116 KB Output is correct
11 Correct 13 ms 27860 KB Output is correct
12 Correct 12 ms 27676 KB Output is correct
13 Correct 13 ms 27696 KB Output is correct
14 Correct 14 ms 28012 KB Output is correct
15 Correct 12 ms 27732 KB Output is correct
16 Correct 11 ms 27768 KB Output is correct
17 Incorrect 11 ms 27604 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 27604 KB Output is correct
2 Correct 10 ms 27732 KB Output is correct
3 Correct 11 ms 27808 KB Output is correct
4 Correct 15 ms 27860 KB Output is correct
5 Correct 14 ms 28116 KB Output is correct
6 Correct 13 ms 27860 KB Output is correct
7 Correct 12 ms 27676 KB Output is correct
8 Correct 13 ms 27696 KB Output is correct
9 Correct 14 ms 28012 KB Output is correct
10 Correct 12 ms 27732 KB Output is correct
11 Correct 11 ms 27768 KB Output is correct
12 Incorrect 11 ms 27604 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 27604 KB Output is correct
2 Correct 10 ms 27732 KB Output is correct
3 Correct 11 ms 27808 KB Output is correct
4 Correct 15 ms 27860 KB Output is correct
5 Correct 14 ms 28116 KB Output is correct
6 Correct 13 ms 27860 KB Output is correct
7 Correct 12 ms 27676 KB Output is correct
8 Correct 13 ms 27696 KB Output is correct
9 Correct 14 ms 28012 KB Output is correct
10 Correct 12 ms 27732 KB Output is correct
11 Correct 11 ms 27768 KB Output is correct
12 Incorrect 11 ms 27604 KB Output isn't correct
13 Halted 0 ms 0 KB -