oj.uz

Submission #642995

# Submission time Handle Problem Language Result Execution time Memory
642995 2022-09-21T02:43:00 Z CyberSleeper Monthly railway pass (LMIO18_menesinis_bilietas) C++17
100 / 100
 666 ms 102912 KB 
#include <bits/stdc++.h>
using namespace std;

const int MX=500007;

int N, M, group[MX], sz[MX], cnt_group, ans;
vector<int> bus[MX], tr[MX];
set<int> adj[MX];

void DFS(int x){
    group[x]=cnt_group;
    sz[cnt_group]++;
    for(int i:tr[x]){
        if(group[i])
            continue;
        DFS(i);
    }
}

int main(){
    cin >> N >> M;
    for(int i=0; i<M; i++){
        int u, v;
        char w;
        cin >> u >> v >> w;
        if(u == v)
            continue;
        if(w == 'A'){
            bus[u].push_back(v);
            bus[v].push_back(u);
        }else{
            tr[u].push_back(v);
            tr[v].push_back(u);
        }
    }
    for(int i=1; i<=N; i++){
        if(!group[i]){
            cnt_group++;
            DFS(i);
        }
    }
    for(int i=1; i<=N; i++){
        for(int j:bus[i]){
            if(group[i] != group[j])
                adj[group[i]].insert(group[j]);
        }
    }
    for(int i=1; i<=N; i++){
        if(adj[i].size()==cnt_group-1)
            ans+=sz[i];
    }
    cout << ans << endl;
}

Compilation message

menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:49:25: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |         if(adj[i].size()==cnt_group-1)
      |            ~~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 63512 KB Output is correct
2 Correct 22 ms 47188 KB Output is correct
3 Correct 25 ms 47224 KB Output is correct
4 Correct 29 ms 50900 KB Output is correct
5 Correct 22 ms 47316 KB Output is correct
6 Correct 140 ms 50068 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 50900 KB Output is correct
2 Correct 22 ms 47316 KB Output is correct
3 Correct 22 ms 47188 KB Output is correct
4 Correct 23 ms 47384 KB Output is correct
5 Correct 27 ms 47956 KB Output is correct
6 Correct 333 ms 82432 KB Output is correct
7 Correct 666 ms 102912 KB Output is correct
8 Correct 44 ms 49312 KB Output is correct
9 Correct 46 ms 50488 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47188 KB Output is correct
2 Correct 25 ms 47224 KB Output is correct
3 Correct 22 ms 47188 KB Output is correct
4 Correct 23 ms 47384 KB Output is correct
5 Correct 27 ms 47956 KB Output is correct
6 Correct 22 ms 47268 KB Output is correct
7 Correct 23 ms 47312 KB Output is correct
8 Correct 24 ms 47316 KB Output is correct
9 Correct 25 ms 47324 KB Output is correct
10 Correct 26 ms 47444 KB Output is correct
11 Correct 26 ms 47512 KB Output is correct
12 Correct 22 ms 47300 KB Output is correct
13 Correct 25 ms 47268 KB Output is correct
14 Correct 30 ms 47648 KB Output is correct
15 Correct 22 ms 47172 KB Output is correct
16 Correct 24 ms 47360 KB Output is correct
17 Correct 22 ms 47188 KB Output is correct
18 Correct 23 ms 47316 KB Output is correct
19 Correct 23 ms 47316 KB Output is correct
20 Correct 24 ms 47408 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47268 KB Output is correct
2 Correct 23 ms 47312 KB Output is correct
3 Correct 24 ms 47316 KB Output is correct
4 Correct 25 ms 47324 KB Output is correct
5 Correct 26 ms 47444 KB Output is correct
6 Correct 26 ms 47512 KB Output is correct
7 Correct 22 ms 47300 KB Output is correct
8 Correct 25 ms 47268 KB Output is correct
9 Correct 30 ms 47648 KB Output is correct
10 Correct 22 ms 47172 KB Output is correct
11 Correct 24 ms 47360 KB Output is correct
12 Correct 22 ms 47188 KB Output is correct
13 Correct 23 ms 47316 KB Output is correct
14 Correct 23 ms 47316 KB Output is correct
15 Correct 24 ms 47408 KB Output is correct
16 Correct 22 ms 47188 KB Output is correct
17 Correct 25 ms 47224 KB Output is correct
18 Correct 22 ms 47188 KB Output is correct
19 Correct 23 ms 47384 KB Output is correct
20 Correct 27 ms 47956 KB Output is correct
21 Correct 22 ms 47316 KB Output is correct
22 Correct 44 ms 49312 KB Output is correct
23 Correct 46 ms 50488 KB Output is correct
24 Correct 140 ms 50068 KB Output is correct
25 Correct 42 ms 47768 KB Output is correct
26 Correct 260 ms 52644 KB Output is correct
27 Correct 104 ms 49176 KB Output is correct
28 Correct 160 ms 60836 KB Output is correct
29 Correct 87 ms 49168 KB Output is correct
30 Correct 178 ms 59212 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47268 KB Output is correct
2 Correct 23 ms 47312 KB Output is correct
3 Correct 24 ms 47316 KB Output is correct
4 Correct 25 ms 47324 KB Output is correct
5 Correct 26 ms 47444 KB Output is correct
6 Correct 26 ms 47512 KB Output is correct
7 Correct 22 ms 47300 KB Output is correct
8 Correct 25 ms 47268 KB Output is correct
9 Correct 30 ms 47648 KB Output is correct
10 Correct 22 ms 47172 KB Output is correct
11 Correct 24 ms 47360 KB Output is correct
12 Correct 22 ms 47188 KB Output is correct
13 Correct 23 ms 47316 KB Output is correct
14 Correct 23 ms 47316 KB Output is correct
15 Correct 24 ms 47408 KB Output is correct
16 Correct 42 ms 47768 KB Output is correct
17 Correct 260 ms 52644 KB Output is correct
18 Correct 104 ms 49176 KB Output is correct
19 Correct 160 ms 60836 KB Output is correct
20 Correct 87 ms 49168 KB Output is correct
21 Correct 178 ms 59212 KB Output is correct
22 Correct 501 ms 63512 KB Output is correct
23 Correct 22 ms 47188 KB Output is correct
24 Correct 25 ms 47224 KB Output is correct
25 Correct 29 ms 50900 KB Output is correct
26 Correct 22 ms 47188 KB Output is correct
27 Correct 23 ms 47384 KB Output is correct
28 Correct 27 ms 47956 KB Output is correct
29 Correct 22 ms 47316 KB Output is correct
30 Correct 333 ms 82432 KB Output is correct
31 Correct 666 ms 102912 KB Output is correct
32 Correct 44 ms 49312 KB Output is correct
33 Correct 46 ms 50488 KB Output is correct
34 Correct 140 ms 50068 KB Output is correct
35 Correct 75 ms 50612 KB Output is correct
36 Correct 455 ms 60664 KB Output is correct
37 Correct 227 ms 54604 KB Output is correct