# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
642669 | 2022-09-20T10:39:23 Z | joshjms | Monthly railway pass (LMIO18_menesinis_bilietas) | C++14 | 219 ms | 53768 KB |
#include <bits/stdc++.h> using namespace std; #define ld long double #define pb push_back #define fi first #define se second #define debug(x) cout << #x << " => " << x << "\n" const int mod = 998244353; const ld E = 1e-4; struct Edge { int u, v; char c; } a[500005]; int n, m, sum; vector <int> g[500005]; int par[500005], sz[500005]; vector <int> e[500005]; int find(int u) { if(u == par[u]) return u; return par[u] = find(par[u]); } int join(int u, int v) { u = find(u); v = find(v); if(u == v) return 0; if(e[u].size() > e[v].size()) { par[v] = u; sz[u] += sz[v]; for(auto i : e[v]) e[u].pb(i); } else { par[u] = v; sz[v] += sz[u]; for(auto i : e[u]) e[v].pb(i); } return 1; } int ans[500005]; void solve () { cin >> n >> m; for(int i = 1; i <= n; i++) { par[i] = i; sz[i] = 1; ans[i] = -1; } for(int i = 1; i <= m; i++) { cin >> a[i].u >> a[i].v >> a[i].c; } for(int i = 1; i <= m; i++) { if(a[i].c == 'A') { e[a[i].u].pb(a[i].v); e[a[i].v].pb(a[i].u); } } for(int i = 1; i <= m; i++) { if(a[i].c == 'T') { join(a[i].u, a[i].v); } } for(int i = 1; i <= n; i++) { for(int j = 0; j < e[i].size(); j++) e[i][j] = find(e[i][j]); sort(e[i].begin(), e[i].end()); e[i].resize(unique(e[i].begin(), e[i].end()) - e[i].begin()); } for(int i = 1; i <= n; i++) { int u = find(i); if(ans[u] == -1) { int s = sz[u]; for(auto j : e[u]) { s += sz[find(j)]; } if(s == n) ans[u] = 1; else ans[u] = 0; } sum += ans[u]; } cout << sum << "\n"; } signed main () { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve (); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 137 ms | 39532 KB | Output is correct |
2 | Correct | 15 ms | 23764 KB | Output is correct |
3 | Correct | 13 ms | 23764 KB | Output is correct |
4 | Correct | 18 ms | 29280 KB | Output is correct |
5 | Correct | 12 ms | 23892 KB | Output is correct |
6 | Correct | 48 ms | 28572 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 29280 KB | Output is correct |
2 | Correct | 12 ms | 23892 KB | Output is correct |
3 | Correct | 12 ms | 23744 KB | Output is correct |
4 | Correct | 12 ms | 23800 KB | Output is correct |
5 | Correct | 14 ms | 24040 KB | Output is correct |
6 | Correct | 124 ms | 36528 KB | Output is correct |
7 | Correct | 219 ms | 53768 KB | Output is correct |
8 | Correct | 17 ms | 24788 KB | Output is correct |
9 | Correct | 21 ms | 25200 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 23764 KB | Output is correct |
2 | Correct | 13 ms | 23764 KB | Output is correct |
3 | Correct | 12 ms | 23744 KB | Output is correct |
4 | Correct | 12 ms | 23800 KB | Output is correct |
5 | Correct | 14 ms | 24040 KB | Output is correct |
6 | Correct | 13 ms | 23716 KB | Output is correct |
7 | Correct | 12 ms | 23756 KB | Output is correct |
8 | Correct | 16 ms | 23964 KB | Output is correct |
9 | Correct | 13 ms | 24020 KB | Output is correct |
10 | Incorrect | 16 ms | 24276 KB | Output isn't correct |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 23716 KB | Output is correct |
2 | Correct | 12 ms | 23756 KB | Output is correct |
3 | Correct | 16 ms | 23964 KB | Output is correct |
4 | Correct | 13 ms | 24020 KB | Output is correct |
5 | Incorrect | 16 ms | 24276 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 23716 KB | Output is correct |
2 | Correct | 12 ms | 23756 KB | Output is correct |
3 | Correct | 16 ms | 23964 KB | Output is correct |
4 | Correct | 13 ms | 24020 KB | Output is correct |
5 | Incorrect | 16 ms | 24276 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |