oj.uz

Submission #642800

# Submission time Handle Problem Language Result Execution time Memory
642800 2022-09-20T14:08:25 Z sanstzu Monthly railway pass (LMIO18_menesinis_bilietas) C++14
16 / 100
 675 ms 103984 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> train[500069], bus[500069];
set<int> adj[500069];
int par[500069], sz[500069];
bool visited[500069];
int pars;

void init(){
    for(int i=0; i<500069; i++){
        par[i] = i;
        sz[i] = 1;
        visited[i] = 0;
    }
}

int fp(int x){
    if(par[x]==x) return x;
    else return par[x]=fp(par[x]);
}

void merge(int x, int y){
    int px, py;
    px = fp(x), py = fp(y);
    if(sz[px] > sz[py]){
        par[py] = px;
        sz[px] += sz[py];
    } else {
        par[px] = py;
        sz[py] += sz[px];
    }
    pars--;
}

void search(int x){
    if(visited[x]) return;
    visited[x] = true;
    for(int i: train[x]){
        if(visited[i]) continue;
        if(fp(x) != fp(i)) merge(x,i);
        search(x);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cout.tie(0); cin.tie(0);
    init();
    int n,m; cin >> n >> m;
    pars = n;
    for(int i=0; i<m; i++){
        int a,b; char c;
        cin >> a >> b >> c;
        a--; b--;
        if(c=='A'){
            bus[a].push_back(b);
            bus[b].push_back(a);
        } else {
            train[a].push_back(b);
            train[b].push_back(a);
        }
    }
    for(int i=0; i<n; i++){
        if(!visited[i])search(i);
    }

    for(int i=0; i<n; i++){
        for(int j: bus[i]){
            int px = fp(i), py = fp(j);
            adj[px].insert(py);
            adj[py].insert(px);
        }
    }
    int ans = 0;
    if(pars == 1){
        cout << n << "\n";
        return 0;
    }
    for(int i=0; i<n; i++){
        if(fp(i)!=i) continue;
        //if(adj[i].size() != 0) cout << i << " " << adj[i].size() << "\n";
        if(((int)adj[i].size()) >= pars-1) ans += sz[fp(i)];
    }
    cout << ans << "\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 62264 KB Output is correct
2 Correct 24 ms 51668 KB Output is correct
3 Correct 25 ms 51664 KB Output is correct
4 Correct 29 ms 51632 KB Output is correct
5 Correct 23 ms 51688 KB Output is correct
6 Correct 66 ms 54052 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 51632 KB Output is correct
2 Correct 23 ms 51688 KB Output is correct
3 Correct 25 ms 51584 KB Output is correct
4 Correct 25 ms 51800 KB Output is correct
5 Correct 28 ms 52428 KB Output is correct
6 Correct 425 ms 86408 KB Output is correct
7 Correct 675 ms 103984 KB Output is correct
8 Correct 40 ms 53588 KB Output is correct
9 Correct 48 ms 54756 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 51668 KB Output is correct
2 Correct 25 ms 51664 KB Output is correct
3 Correct 25 ms 51584 KB Output is correct
4 Correct 25 ms 51800 KB Output is correct
5 Correct 28 ms 52428 KB Output is correct
6 Correct 25 ms 51612 KB Output is correct
7 Correct 24 ms 51568 KB Output is correct
8 Correct 25 ms 51668 KB Output is correct
9 Correct 26 ms 51740 KB Output is correct
10 Correct 29 ms 51872 KB Output is correct
11 Correct 27 ms 52064 KB Output is correct
12 Correct 24 ms 51620 KB Output is correct
13 Correct 24 ms 51720 KB Output is correct
14 Correct 29 ms 52164 KB Output is correct
15 Correct 24 ms 51608 KB Output is correct
16 Correct 25 ms 51728 KB Output is correct
17 Correct 27 ms 51596 KB Output is correct
18 Correct 27 ms 51788 KB Output is correct
19 Incorrect 25 ms 51716 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 51612 KB Output is correct
2 Correct 24 ms 51568 KB Output is correct
3 Correct 25 ms 51668 KB Output is correct
4 Correct 26 ms 51740 KB Output is correct
5 Correct 29 ms 51872 KB Output is correct
6 Correct 27 ms 52064 KB Output is correct
7 Correct 24 ms 51620 KB Output is correct
8 Correct 24 ms 51720 KB Output is correct
9 Correct 29 ms 52164 KB Output is correct
10 Correct 24 ms 51608 KB Output is correct
11 Correct 25 ms 51728 KB Output is correct
12 Correct 27 ms 51596 KB Output is correct
13 Correct 27 ms 51788 KB Output is correct
14 Incorrect 25 ms 51716 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 51612 KB Output is correct
2 Correct 24 ms 51568 KB Output is correct
3 Correct 25 ms 51668 KB Output is correct
4 Correct 26 ms 51740 KB Output is correct
5 Correct 29 ms 51872 KB Output is correct
6 Correct 27 ms 52064 KB Output is correct
7 Correct 24 ms 51620 KB Output is correct
8 Correct 24 ms 51720 KB Output is correct
9 Correct 29 ms 52164 KB Output is correct
10 Correct 24 ms 51608 KB Output is correct
11 Correct 25 ms 51728 KB Output is correct
12 Correct 27 ms 51596 KB Output is correct
13 Correct 27 ms 51788 KB Output is correct
14 Incorrect 25 ms 51716 KB Output isn't correct
15 Halted 0 ms 0 KB -