# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
885348 | 2023-12-09T14:00:29 Z | Isam | Monthly railway pass (LMIO18_menesinis_bilietas) | C++17 | 389 ms | 117756 KB |
#include<bits/stdc++.h> #ifdef DEBUG #include "debug.h" #else #define debug(...) void(37) #endif using namespace std; constexpr int sz = 500000; int sizel[sz], fa[sz], N, M; int find_set(int v){ if(fa[v] == v) return v; return fa[v] = find_set(fa[v]); } inline void Union(int x, int y){ x = find_set(x); y = find_set(y); if(x ^ y){ if(sizel[x] > sizel[y]) swap(x, y); fa[x] = fa[y]; sizel[y] += sizel[x]; } return; } inline void init(){ for(register int i = 1; i <= N; ++i) sizel[i] = 1, fa[i] = i; return; } string ch; vector<pair<int, int>> laaa; unordered_set<int> adj[sz]; signed main(){ ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> N >> M; init(); for(register int i = 1, x, y; i <= M; ++i){ cin >> x >> y >> ch; if(ch[0] == 'T'){ Union(x, y); }else{ laaa.emplace_back((pair<int, int>){x, y}); } } vector<int> A; for(register int i = 1; i <= N; ++i){ if(find_set(i) == i) A.emplace_back(i); } for(register int i = 0; i < (int)laaa.size(); ++i){ int x{laaa[i].first}, y{laaa[i].second}; x = find_set(x), y = find_set(y); if(x == y) continue; adj[x].insert(y); adj[y].insert(x); } int components{(int)A.size()}, ans(0); for(register int i = 0; i < components; ++i){ if((int)adj[A[i]].size() == components - 1) ans += sizel[A[i]]; } cout << ans << '\n'; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 104 ms | 38176 KB | Output is correct |
2 | Correct | 7 ms | 31320 KB | Output is correct |
3 | Correct | 7 ms | 31324 KB | Output is correct |
4 | Correct | 12 ms | 33752 KB | Output is correct |
5 | Correct | 7 ms | 31540 KB | Output is correct |
6 | Correct | 38 ms | 33620 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 33752 KB | Output is correct |
2 | Correct | 7 ms | 31540 KB | Output is correct |
3 | Correct | 7 ms | 31324 KB | Output is correct |
4 | Correct | 7 ms | 31312 KB | Output is correct |
5 | Correct | 10 ms | 32092 KB | Output is correct |
6 | Correct | 322 ms | 69588 KB | Output is correct |
7 | Correct | 389 ms | 117756 KB | Output is correct |
8 | Correct | 15 ms | 34396 KB | Output is correct |
9 | Correct | 22 ms | 35860 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 31320 KB | Output is correct |
2 | Correct | 7 ms | 31324 KB | Output is correct |
3 | Correct | 7 ms | 31324 KB | Output is correct |
4 | Correct | 7 ms | 31312 KB | Output is correct |
5 | Correct | 10 ms | 32092 KB | Output is correct |
6 | Correct | 7 ms | 31616 KB | Output is correct |
7 | Correct | 7 ms | 31424 KB | Output is correct |
8 | Correct | 8 ms | 31324 KB | Output is correct |
9 | Correct | 8 ms | 31324 KB | Output is correct |
10 | Correct | 9 ms | 31612 KB | Output is correct |
11 | Correct | 8 ms | 31580 KB | Output is correct |
12 | Correct | 7 ms | 31328 KB | Output is correct |
13 | Correct | 7 ms | 31324 KB | Output is correct |
14 | Correct | 10 ms | 31620 KB | Output is correct |
15 | Correct | 7 ms | 31604 KB | Output is correct |
16 | Correct | 7 ms | 31472 KB | Output is correct |
17 | Correct | 7 ms | 31524 KB | Output is correct |
18 | Correct | 8 ms | 31324 KB | Output is correct |
19 | Correct | 7 ms | 31324 KB | Output is correct |
20 | Correct | 9 ms | 31324 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 31616 KB | Output is correct |
2 | Correct | 7 ms | 31424 KB | Output is correct |
3 | Correct | 8 ms | 31324 KB | Output is correct |
4 | Correct | 8 ms | 31324 KB | Output is correct |
5 | Correct | 9 ms | 31612 KB | Output is correct |
6 | Correct | 8 ms | 31580 KB | Output is correct |
7 | Correct | 7 ms | 31328 KB | Output is correct |
8 | Correct | 7 ms | 31324 KB | Output is correct |
9 | Correct | 10 ms | 31620 KB | Output is correct |
10 | Correct | 7 ms | 31604 KB | Output is correct |
11 | Correct | 7 ms | 31472 KB | Output is correct |
12 | Correct | 7 ms | 31524 KB | Output is correct |
13 | Correct | 8 ms | 31324 KB | Output is correct |
14 | Correct | 7 ms | 31324 KB | Output is correct |
15 | Correct | 9 ms | 31324 KB | Output is correct |
16 | Correct | 7 ms | 31320 KB | Output is correct |
17 | Correct | 7 ms | 31324 KB | Output is correct |
18 | Correct | 7 ms | 31324 KB | Output is correct |
19 | Correct | 7 ms | 31312 KB | Output is correct |
20 | Correct | 10 ms | 32092 KB | Output is correct |
21 | Correct | 7 ms | 31540 KB | Output is correct |
22 | Correct | 15 ms | 34396 KB | Output is correct |
23 | Correct | 22 ms | 35860 KB | Output is correct |
24 | Correct | 38 ms | 33620 KB | Output is correct |
25 | Correct | 13 ms | 32076 KB | Output is correct |
26 | Correct | 81 ms | 39968 KB | Output is correct |
27 | Correct | 36 ms | 34740 KB | Output is correct |
28 | Correct | 81 ms | 44624 KB | Output is correct |
29 | Correct | 29 ms | 33940 KB | Output is correct |
30 | Correct | 86 ms | 43116 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 31616 KB | Output is correct |
2 | Correct | 7 ms | 31424 KB | Output is correct |
3 | Correct | 8 ms | 31324 KB | Output is correct |
4 | Correct | 8 ms | 31324 KB | Output is correct |
5 | Correct | 9 ms | 31612 KB | Output is correct |
6 | Correct | 8 ms | 31580 KB | Output is correct |
7 | Correct | 7 ms | 31328 KB | Output is correct |
8 | Correct | 7 ms | 31324 KB | Output is correct |
9 | Correct | 10 ms | 31620 KB | Output is correct |
10 | Correct | 7 ms | 31604 KB | Output is correct |
11 | Correct | 7 ms | 31472 KB | Output is correct |
12 | Correct | 7 ms | 31524 KB | Output is correct |
13 | Correct | 8 ms | 31324 KB | Output is correct |
14 | Correct | 7 ms | 31324 KB | Output is correct |
15 | Correct | 9 ms | 31324 KB | Output is correct |
16 | Correct | 13 ms | 32076 KB | Output is correct |
17 | Correct | 81 ms | 39968 KB | Output is correct |
18 | Correct | 36 ms | 34740 KB | Output is correct |
19 | Correct | 81 ms | 44624 KB | Output is correct |
20 | Correct | 29 ms | 33940 KB | Output is correct |
21 | Correct | 86 ms | 43116 KB | Output is correct |
22 | Correct | 104 ms | 38176 KB | Output is correct |
23 | Correct | 7 ms | 31320 KB | Output is correct |
24 | Correct | 7 ms | 31324 KB | Output is correct |
25 | Correct | 12 ms | 33752 KB | Output is correct |
26 | Correct | 7 ms | 31324 KB | Output is correct |
27 | Correct | 7 ms | 31312 KB | Output is correct |
28 | Correct | 10 ms | 32092 KB | Output is correct |
29 | Correct | 7 ms | 31540 KB | Output is correct |
30 | Correct | 322 ms | 69588 KB | Output is correct |
31 | Correct | 389 ms | 117756 KB | Output is correct |
32 | Correct | 15 ms | 34396 KB | Output is correct |
33 | Correct | 22 ms | 35860 KB | Output is correct |
34 | Correct | 38 ms | 33620 KB | Output is correct |
35 | Correct | 24 ms | 33748 KB | Output is correct |
36 | Correct | 120 ms | 45308 KB | Output is correct |
37 | Correct | 56 ms | 34472 KB | Output is correct |