oj.uz

Submission #247020

# Submission time Handle Problem Language Result Execution time Memory
247020 2020-07-10T19:20:16 Z dolphingarlic Monthly railway pass (LMIO18_menesinis_bilietas) C++14
16 / 100
 730 ms 92000 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

vector<pair<int, int>> bus;
int cmp[500001];
set<int> graph[500001];

int find(int A) {
    while (A != cmp[A]) cmp[A] = cmp[cmp[A]], A = cmp[A];
    return A;
}

void onion(int A, int B) {
    cmp[find(A)] = cmp[find(B)];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    iota(cmp + 1, cmp + n + 1, 1);
    while (m--) {
        int u, v;
        char t;
        cin >> u >> v >> t;
        if (t == 'A') bus.push_back({u, v});
        else onion(u, v);
    }
    for (pair<int, int> i : bus) {
        graph[find(i.first)].insert(find(i.second));
        graph[find(i.second)].insert(find(i.first));
    }

    set<int> cmpset;
    FOR(i, 1, n + 1) cmpset.insert(find(i));

    int ans = 0;
    FOR(i, 1, n + 1) if (graph[find(i)].size() == cmpset.size() - 1) ans++;
    cout << ans;
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 31864 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 19 ms 23808 KB Output is correct
4 Correct 126 ms 47736 KB Output is correct
5 Correct 20 ms 24448 KB Output is correct
6 Correct 56 ms 26232 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 47736 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 19 ms 23936 KB Output is correct
4 Correct 26 ms 24704 KB Output is correct
5 Correct 20 ms 24448 KB Output is correct
6 Correct 567 ms 64096 KB Output is correct
7 Correct 730 ms 92000 KB Output is correct
8 Correct 31 ms 26240 KB Output is correct
9 Correct 37 ms 27768 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 19 ms 23936 KB Output is correct
4 Correct 21 ms 23936 KB Output is correct
5 Incorrect 21 ms 24064 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 19 ms 23936 KB Output is correct
4 Correct 21 ms 23936 KB Output is correct
5 Incorrect 21 ms 24064 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 19 ms 23936 KB Output is correct
4 Correct 21 ms 23936 KB Output is correct
5 Incorrect 21 ms 24064 KB Output isn't correct
6 Halted 0 ms 0 KB -