oj.uz

Submission #642990

# Submission time Handle Problem Language Result Execution time Memory
642990 2022-09-21T02:31:35 Z CyberSleeper Monthly railway pass (LMIO18_menesinis_bilietas) C++17
100 / 100
 555 ms 102744 KB 
#include <bits/stdc++.h>
#define fastio      ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define debug(x)    cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl
#define all(x)      x.begin(), x.end()
#define fi          first
#define se          second
#define mp          make_pair
#define pb          push_back
#define ll          long long
#define ull         unsigned long long
#define pll         pair<ll, ll>
#define pii         pair<ll, ll>
#define ld          long double
#define nl          '\n'
#define tb          '\t'
#define sp          ' '
#define sqr(x)      (x)*(x)
#define arr3        array<ll, 3>
#define arr4        array<ll, 4>
using namespace std;
 
const ll MX=500007, MOD=1000000007, BLOCK=333, INF=1e9+7, LG=62, KEY1=177013, KEY2=353707;
const ll INFF=1000000000000000007;
const ld ERR=1e-6;

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

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

int main(){
    fastio;
    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].pb(v);
            bus[v].pb(u);
        }else{
            tr[u].pb(v);
            tr[v].pb(u);
        }
    }
    for(int i=1; i<=N; i++){
        if(!group[i]){
            cnt++;
            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-1)
            ans+=sz[i];
    }
    cout << ans << nl;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 63628 KB Output is correct
2 Correct 24 ms 47280 KB Output is correct
3 Correct 24 ms 47252 KB Output is correct
4 Correct 32 ms 50920 KB Output is correct
5 Correct 24 ms 47380 KB Output is correct
6 Correct 63 ms 49984 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 50920 KB Output is correct
2 Correct 24 ms 47380 KB Output is correct
3 Correct 24 ms 47264 KB Output is correct
4 Correct 27 ms 47356 KB Output is correct
5 Correct 30 ms 48000 KB Output is correct
6 Correct 212 ms 82432 KB Output is correct
7 Correct 555 ms 102744 KB Output is correct
8 Correct 32 ms 49216 KB Output is correct
9 Correct 39 ms 50652 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47280 KB Output is correct
2 Correct 24 ms 47252 KB Output is correct
3 Correct 24 ms 47264 KB Output is correct
4 Correct 27 ms 47356 KB Output is correct
5 Correct 30 ms 48000 KB Output is correct
6 Correct 26 ms 47316 KB Output is correct
7 Correct 29 ms 47208 KB Output is correct
8 Correct 27 ms 47316 KB Output is correct
9 Correct 28 ms 47316 KB Output is correct
10 Correct 25 ms 47436 KB Output is correct
11 Correct 25 ms 47632 KB Output is correct
12 Correct 24 ms 47304 KB Output is correct
13 Correct 27 ms 47328 KB Output is correct
14 Correct 29 ms 47680 KB Output is correct
15 Correct 28 ms 47280 KB Output is correct
16 Correct 27 ms 47388 KB Output is correct
17 Correct 23 ms 47180 KB Output is correct
18 Correct 24 ms 47416 KB Output is correct
19 Correct 24 ms 47308 KB Output is correct
20 Correct 24 ms 47368 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47316 KB Output is correct
2 Correct 29 ms 47208 KB Output is correct
3 Correct 27 ms 47316 KB Output is correct
4 Correct 28 ms 47316 KB Output is correct
5 Correct 25 ms 47436 KB Output is correct
6 Correct 25 ms 47632 KB Output is correct
7 Correct 24 ms 47304 KB Output is correct
8 Correct 27 ms 47328 KB Output is correct
9 Correct 29 ms 47680 KB Output is correct
10 Correct 28 ms 47280 KB Output is correct
11 Correct 27 ms 47388 KB Output is correct
12 Correct 23 ms 47180 KB Output is correct
13 Correct 24 ms 47416 KB Output is correct
14 Correct 24 ms 47308 KB Output is correct
15 Correct 24 ms 47368 KB Output is correct
16 Correct 24 ms 47280 KB Output is correct
17 Correct 24 ms 47252 KB Output is correct
18 Correct 24 ms 47264 KB Output is correct
19 Correct 27 ms 47356 KB Output is correct
20 Correct 30 ms 48000 KB Output is correct
21 Correct 24 ms 47380 KB Output is correct
22 Correct 32 ms 49216 KB Output is correct
23 Correct 39 ms 50652 KB Output is correct
24 Correct 63 ms 49984 KB Output is correct
25 Correct 31 ms 48080 KB Output is correct
26 Correct 131 ms 56644 KB Output is correct
27 Correct 61 ms 50756 KB Output is correct
28 Correct 100 ms 62836 KB Output is correct
29 Correct 53 ms 50292 KB Output is correct
30 Correct 123 ms 61452 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47316 KB Output is correct
2 Correct 29 ms 47208 KB Output is correct
3 Correct 27 ms 47316 KB Output is correct
4 Correct 28 ms 47316 KB Output is correct
5 Correct 25 ms 47436 KB Output is correct
6 Correct 25 ms 47632 KB Output is correct
7 Correct 24 ms 47304 KB Output is correct
8 Correct 27 ms 47328 KB Output is correct
9 Correct 29 ms 47680 KB Output is correct
10 Correct 28 ms 47280 KB Output is correct
11 Correct 27 ms 47388 KB Output is correct
12 Correct 23 ms 47180 KB Output is correct
13 Correct 24 ms 47416 KB Output is correct
14 Correct 24 ms 47308 KB Output is correct
15 Correct 24 ms 47368 KB Output is correct
16 Correct 31 ms 48080 KB Output is correct
17 Correct 131 ms 56644 KB Output is correct
18 Correct 61 ms 50756 KB Output is correct
19 Correct 100 ms 62836 KB Output is correct
20 Correct 53 ms 50292 KB Output is correct
21 Correct 123 ms 61452 KB Output is correct
22 Correct 365 ms 63628 KB Output is correct
23 Correct 24 ms 47280 KB Output is correct
24 Correct 24 ms 47252 KB Output is correct
25 Correct 32 ms 50920 KB Output is correct
26 Correct 24 ms 47264 KB Output is correct
27 Correct 27 ms 47356 KB Output is correct
28 Correct 30 ms 48000 KB Output is correct
29 Correct 24 ms 47380 KB Output is correct
30 Correct 212 ms 82432 KB Output is correct
31 Correct 555 ms 102744 KB Output is correct
32 Correct 32 ms 49216 KB Output is correct
33 Correct 39 ms 50652 KB Output is correct
34 Correct 63 ms 49984 KB Output is correct
35 Correct 55 ms 51524 KB Output is correct
36 Correct 321 ms 64664 KB Output is correct
37 Correct 163 ms 57584 KB Output is correct