oj.uz

Submission #920866

# Submission time Handle Problem Language Result Execution time Memory
920866 2024-02-03T06:46:03 Z thelegendary08 Monthly railway pass (LMIO18_menesinis_bilietas) C++14
100 / 100
 686 ms 97252 KB 
#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0;i<n;i++)
#define pb push_back
using namespace std;
const int mxn = 500005;
vector<int> adj[mxn];
bool vis[mxn];
vector<int>cur;
void dfs(int u){
    if(vis[u])return;
    vis[u] = 1;
    cur.pb(u);
    for(int x : adj[u])dfs(x);
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>> bus;
    f0r(i, m){
        int a,b;
        cin>>a>>b;
        char c;
        cin>>c;
        if(c == 'T'){
            adj[--a].pb(--b);
            adj[b].pb(a);
        }
        else{
            bus.pb({--a,--b});
        }

    }
    f0r(i,n)vis[i] = 0;
    vector<vector<int>>ccs;
    f0r(i,n){
        if(!vis[i]){
            cur.clear();
            dfs(i);
            ccs.pb(cur);
        }
        //f0r(j,n)cout<<vis[j]<<' ';
        //cout<<'\n';
        //for(int x : cur)cout<<x<<' ';
        //cout<<'\n';


    }
    int component[n];

    f0r(i,ccs.size()){
        for(int x : ccs[i]){
            component[x] = i;
        }
    }

    //the size of component i is just ccs[i].size()

    set<int>adj[ccs.size()];
    for(pair<int,int> p : bus){
        int pa = p.first;
        int pb = p.second;
        if(component[pa] != component[pb]){
            adj[component[pa]].insert(component[pb]);
            adj[component[pb]].insert(component[pa]);
        }

    }

    int ans = 0;
    f0r(i,ccs.size()){
        //cout<<adj[i].size()<<' ';
        if(adj[i].size() == ccs.size() - 1)ans += ccs[i].size();
    }

    cout<<ans;

}

Compilation message

menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:2:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define f0r(i,n) for(int i = 0;i<n;i++)
......
   50 |     f0r(i,ccs.size()){
      |         ~~~~~~~~~~~~             
menesinis_bilietas.cpp:50:5: note: in expansion of macro 'f0r'
   50 |     f0r(i,ccs.size()){
      |     ^~~
menesinis_bilietas.cpp:2:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define f0r(i,n) for(int i = 0;i<n;i++)
......
   70 |     f0r(i,ccs.size()){
      |         ~~~~~~~~~~~~             
menesinis_bilietas.cpp:70:5: note: in expansion of macro 'f0r'
   70 |     f0r(i,ccs.size()){
      |     ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 32564 KB Output is correct
2 Correct 3 ms 12376 KB Output is correct
3 Correct 4 ms 12380 KB Output is correct
4 Correct 48 ms 62312 KB Output is correct
5 Correct 5 ms 13720 KB Output is correct
6 Correct 95 ms 15200 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 62312 KB Output is correct
2 Correct 5 ms 13720 KB Output is correct
3 Correct 4 ms 12380 KB Output is correct
4 Correct 4 ms 12376 KB Output is correct
5 Correct 8 ms 13148 KB Output is correct
6 Correct 637 ms 51700 KB Output is correct
7 Correct 686 ms 97252 KB Output is correct
8 Correct 17 ms 15512 KB Output is correct
9 Correct 25 ms 16912 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12376 KB Output is correct
2 Correct 4 ms 12380 KB Output is correct
3 Correct 4 ms 12380 KB Output is correct
4 Correct 4 ms 12376 KB Output is correct
5 Correct 8 ms 13148 KB Output is correct
6 Correct 3 ms 12376 KB Output is correct
7 Correct 3 ms 12380 KB Output is correct
8 Correct 5 ms 12380 KB Output is correct
9 Correct 7 ms 12380 KB Output is correct
10 Correct 9 ms 12636 KB Output is correct
11 Correct 7 ms 12636 KB Output is correct
12 Correct 3 ms 12380 KB Output is correct
13 Correct 3 ms 12380 KB Output is correct
14 Correct 9 ms 12636 KB Output is correct
15 Correct 3 ms 12380 KB Output is correct
16 Correct 5 ms 12376 KB Output is correct
17 Correct 3 ms 12380 KB Output is correct
18 Correct 5 ms 12636 KB Output is correct
19 Correct 4 ms 12380 KB Output is correct
20 Correct 5 ms 12636 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12376 KB Output is correct
2 Correct 3 ms 12380 KB Output is correct
3 Correct 5 ms 12380 KB Output is correct
4 Correct 7 ms 12380 KB Output is correct
5 Correct 9 ms 12636 KB Output is correct
6 Correct 7 ms 12636 KB Output is correct
7 Correct 3 ms 12380 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 9 ms 12636 KB Output is correct
10 Correct 3 ms 12380 KB Output is correct
11 Correct 5 ms 12376 KB Output is correct
12 Correct 3 ms 12380 KB Output is correct
13 Correct 5 ms 12636 KB Output is correct
14 Correct 4 ms 12380 KB Output is correct
15 Correct 5 ms 12636 KB Output is correct
16 Correct 3 ms 12376 KB Output is correct
17 Correct 4 ms 12380 KB Output is correct
18 Correct 4 ms 12380 KB Output is correct
19 Correct 4 ms 12376 KB Output is correct
20 Correct 8 ms 13148 KB Output is correct
21 Correct 5 ms 13720 KB Output is correct
22 Correct 17 ms 15512 KB Output is correct
23 Correct 25 ms 16912 KB Output is correct
24 Correct 95 ms 15200 KB Output is correct
25 Correct 19 ms 12772 KB Output is correct
26 Correct 222 ms 18368 KB Output is correct
27 Correct 85 ms 14536 KB Output is correct
28 Correct 151 ms 25448 KB Output is correct
29 Correct 59 ms 13776 KB Output is correct
30 Correct 145 ms 23796 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12376 KB Output is correct
2 Correct 3 ms 12380 KB Output is correct
3 Correct 5 ms 12380 KB Output is correct
4 Correct 7 ms 12380 KB Output is correct
5 Correct 9 ms 12636 KB Output is correct
6 Correct 7 ms 12636 KB Output is correct
7 Correct 3 ms 12380 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 9 ms 12636 KB Output is correct
10 Correct 3 ms 12380 KB Output is correct
11 Correct 5 ms 12376 KB Output is correct
12 Correct 3 ms 12380 KB Output is correct
13 Correct 5 ms 12636 KB Output is correct
14 Correct 4 ms 12380 KB Output is correct
15 Correct 5 ms 12636 KB Output is correct
16 Correct 19 ms 12772 KB Output is correct
17 Correct 222 ms 18368 KB Output is correct
18 Correct 85 ms 14536 KB Output is correct
19 Correct 151 ms 25448 KB Output is correct
20 Correct 59 ms 13776 KB Output is correct
21 Correct 145 ms 23796 KB Output is correct
22 Correct 481 ms 32564 KB Output is correct
23 Correct 3 ms 12376 KB Output is correct
24 Correct 4 ms 12380 KB Output is correct
25 Correct 48 ms 62312 KB Output is correct
26 Correct 4 ms 12380 KB Output is correct
27 Correct 4 ms 12376 KB Output is correct
28 Correct 8 ms 13148 KB Output is correct
29 Correct 5 ms 13720 KB Output is correct
30 Correct 637 ms 51700 KB Output is correct
31 Correct 686 ms 97252 KB Output is correct
32 Correct 17 ms 15512 KB Output is correct
33 Correct 25 ms 16912 KB Output is correct
34 Correct 95 ms 15200 KB Output is correct
35 Correct 46 ms 15264 KB Output is correct
36 Correct 317 ms 23472 KB Output is correct
37 Correct 154 ms 20564 KB Output is correct