답안 #639590

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
639590	2022-09-10T17:09:49 Z	LeticiaFCS	Monthly railway pass (LMIO18_menesinis_bilietas)	C++17	100 / 100	1224 ms	81320 KB

menesinis_bilietas

#include "bits/stdc++.h"
#define st first
#define nd second
using lint = int64_t;
constexpr int MOD = int(1e9) + 7;
constexpr int INF = 0x3f3f3f3f;
constexpr int NINF = 0xcfcfcfcf;
constexpr lint LINF = 0x3f3f3f3f3f3f3f3f;
const long double PI = acosl(-1.0);
// Returns -1 if a < b, 0 if a = b and 1 if a > b.
int cmp_double(double a, double b = 0, double eps = 1e-9) {
	return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}
using namespace std;
struct UF {
	vector<int> e, sz;
	UF(int n) : e(n, -1) {}
	bool same_set(int a, int b) { return find(a) == find(b); }
	int size(int x) { return -e[find(x)]; }
	int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
	bool unite(int a, int b) {
		a = find(a), b = find(b);
		if (a == b) return 0;
		if (e[a] > e[b]) swap(a, b);
		e[a] += e[b]; e[b] = a;
		return 1;
	}
};

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	//int __; cin >> __; for( int _ = 1 ; _ <= __ ; _++ ){ }
	int n, m;
	cin>>n>>m;
	using pii = pair<int, int>;
	vector<pii> bus;
	
	UF uf(n);
	
	while(m--){
		int u, v;
		cin>>u>>v;
		u--, v--;
		string type;
		cin>>type;
		if(type == "A"){
			bus.emplace_back(u, v);
		} else {
			uf.unite(u, v);	
		}
	}
	
	map<int, int> compr;
	
	int id = 0;
	for(int u=0; u<n; u++)
		if(!compr.count(uf.find(u)))
			compr[uf.find(u)] = id++;
	
	vector<set<int>> cg(id);
	for(auto &[u, v]: bus){
		u = uf.find(u);
		v = uf.find(v);
		if(u != v){
			cg[compr[u]].insert(compr[v]);
			cg[compr[v]].insert(compr[u]);
		}
	}
	int answer = 0;
	for(auto &[u, c]: compr)
		if((int) cg[c].size() == id-1)
			answer += uf.size(u);
	cout<<answer<<"\n";
	
	return 0;
}
/*
[  ]Leu o problema certo???
[  ]Ver se precisa de long long
[  ]Viu o limite dos fors (é n? é m?)
[  ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[  ]Testar sample
[  ]Testar casos de  borda
[  ]1LL no 1LL << i
[  ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	111 ms	1492 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	159 ms	46244 KB	Output is correct
5	Correct	3 ms	1492 KB	Output is correct
6	Correct	39 ms	348 KB	Output is correct

Subtask #2
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	159 ms	46244 KB	Output is correct
2	Correct	3 ms	1492 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	5 ms	1108 KB	Output is correct
6	Correct	726 ms	38304 KB	Output is correct
7	Correct	1224 ms	81320 KB	Output is correct
8	Correct	15 ms	3272 KB	Output is correct
9	Correct	31 ms	4664 KB	Output is correct

Subtask #3
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	5 ms	1108 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	2 ms	340 KB	Output is correct
9	Correct	2 ms	340 KB	Output is correct
10	Correct	4 ms	468 KB	Output is correct
11	Correct	4 ms	584 KB	Output is correct
12	Correct	1 ms	320 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	6 ms	724 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	2 ms	468 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	2 ms	340 KB	Output is correct

Subtask #4
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	2 ms	340 KB	Output is correct
5	Correct	4 ms	468 KB	Output is correct
6	Correct	4 ms	584 KB	Output is correct
7	Correct	1 ms	320 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	6 ms	724 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	2 ms	468 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	2 ms	340 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	5 ms	1108 KB	Output is correct
21	Correct	3 ms	1492 KB	Output is correct
22	Correct	15 ms	3272 KB	Output is correct
23	Correct	31 ms	4664 KB	Output is correct
24	Correct	39 ms	348 KB	Output is correct
25	Correct	13 ms	972 KB	Output is correct
26	Correct	195 ms	8132 KB	Output is correct
27	Correct	67 ms	3968 KB	Output is correct
28	Correct	240 ms	15300 KB	Output is correct
29	Correct	68 ms	2836 KB	Output is correct
30	Correct	164 ms	13288 KB	Output is correct

Subtask #5
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	2 ms	340 KB	Output is correct
5	Correct	4 ms	468 KB	Output is correct
6	Correct	4 ms	584 KB	Output is correct
7	Correct	1 ms	320 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	6 ms	724 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	2 ms	468 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	2 ms	340 KB	Output is correct
16	Correct	13 ms	972 KB	Output is correct
17	Correct	195 ms	8132 KB	Output is correct
18	Correct	67 ms	3968 KB	Output is correct
19	Correct	240 ms	15300 KB	Output is correct
20	Correct	68 ms	2836 KB	Output is correct
21	Correct	164 ms	13288 KB	Output is correct
22	Correct	111 ms	1492 KB	Output is correct
23	Correct	0 ms	212 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	159 ms	46244 KB	Output is correct
26	Correct	0 ms	212 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	5 ms	1108 KB	Output is correct
29	Correct	3 ms	1492 KB	Output is correct
30	Correct	726 ms	38304 KB	Output is correct
31	Correct	1224 ms	81320 KB	Output is correct
32	Correct	15 ms	3272 KB	Output is correct
33	Correct	31 ms	4664 KB	Output is correct
34	Correct	39 ms	348 KB	Output is correct
35	Correct	33 ms	3104 KB	Output is correct
36	Correct	278 ms	13956 KB	Output is correct
37	Correct	68 ms	4188 KB	Output is correct

답안 #639590

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 6.0 / 6.0

Subtask #3 30.0 / 30.0

Subtask #4 35.0 / 35.0

Subtask #5 19.0 / 19.0

Subtask #1
10.0 / 10.0

Subtask #2
6.0 / 6.0

Subtask #3
30.0 / 30.0

Subtask #4
35.0 / 35.0

Subtask #5
19.0 / 19.0