oj.uz

Submission #642803

# Submission time Handle Problem Language Result Execution time Memory
642803 2022-09-20T14:14:56 Z sanstzu Monthly railway pass (LMIO18_menesinis_bilietas) C++14
16 / 100
 668 ms 104116 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);
            //cout << px << " " << py << "\n";
            adj[px].insert(py);
            adj[py].insert(px);
        }
    }
    int ans = 0;
    /*
    if(pars == 1){
        cout << n << "\n";
        return 0;
    }
    */
    //cout << pars << "\n";
    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 292 ms 62160 KB Output is correct
2 Correct 26 ms 51704 KB Output is correct
3 Correct 29 ms 51660 KB Output is correct
4 Correct 29 ms 51668 KB Output is correct
5 Correct 24 ms 51668 KB Output is correct
6 Correct 68 ms 54092 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 51668 KB Output is correct
2 Correct 24 ms 51668 KB Output is correct
3 Correct 25 ms 51548 KB Output is correct
4 Correct 24 ms 51708 KB Output is correct
5 Correct 29 ms 52444 KB Output is correct
6 Correct 412 ms 86464 KB Output is correct
7 Correct 668 ms 104116 KB Output is correct
8 Correct 35 ms 53568 KB Output is correct
9 Correct 45 ms 54836 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 51704 KB Output is correct
2 Correct 29 ms 51660 KB Output is correct
3 Correct 25 ms 51548 KB Output is correct
4 Correct 24 ms 51708 KB Output is correct
5 Correct 29 ms 52444 KB Output is correct
6 Correct 26 ms 51668 KB Output is correct
7 Correct 29 ms 51564 KB Output is correct
8 Correct 31 ms 51740 KB Output is correct
9 Correct 31 ms 51668 KB Output is correct
10 Correct 27 ms 51796 KB Output is correct
11 Correct 26 ms 51980 KB Output is correct
12 Correct 24 ms 51736 KB Output is correct
13 Correct 24 ms 51688 KB Output is correct
14 Correct 28 ms 52052 KB Output is correct
15 Correct 24 ms 51620 KB Output is correct
16 Correct 25 ms 51668 KB Output is correct
17 Correct 24 ms 51588 KB Output is correct
18 Correct 24 ms 51836 KB Output is correct
19 Incorrect 24 ms 51692 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 51668 KB Output is correct
2 Correct 29 ms 51564 KB Output is correct
3 Correct 31 ms 51740 KB Output is correct
4 Correct 31 ms 51668 KB Output is correct
5 Correct 27 ms 51796 KB Output is correct
6 Correct 26 ms 51980 KB Output is correct
7 Correct 24 ms 51736 KB Output is correct
8 Correct 24 ms 51688 KB Output is correct
9 Correct 28 ms 52052 KB Output is correct
10 Correct 24 ms 51620 KB Output is correct
11 Correct 25 ms 51668 KB Output is correct
12 Correct 24 ms 51588 KB Output is correct
13 Correct 24 ms 51836 KB Output is correct
14 Incorrect 24 ms 51692 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 51668 KB Output is correct
2 Correct 29 ms 51564 KB Output is correct
3 Correct 31 ms 51740 KB Output is correct
4 Correct 31 ms 51668 KB Output is correct
5 Correct 27 ms 51796 KB Output is correct
6 Correct 26 ms 51980 KB Output is correct
7 Correct 24 ms 51736 KB Output is correct
8 Correct 24 ms 51688 KB Output is correct
9 Correct 28 ms 52052 KB Output is correct
10 Correct 24 ms 51620 KB Output is correct
11 Correct 25 ms 51668 KB Output is correct
12 Correct 24 ms 51588 KB Output is correct
13 Correct 24 ms 51836 KB Output is correct
14 Incorrect 24 ms 51692 KB Output isn't correct
15 Halted 0 ms 0 KB -