oj.uz

Submission #382150

# Submission time Handle Problem Language Result Execution time Memory
382150 2021-03-26T15:26:33 Z mohamedsobhi777 Monthly railway pass (LMIO18_menesinis_bilietas) C++14
65 / 100
 144 ms 16108 KB 
#include <bits/stdc++.h>

using namespace std;

#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define lb lower_bound
#define ub upper_bound

using ll = long long;
using ld = long double;

const int N = 1e5 + 7;
const ll mod = 1e9 + 7;

int n, m;
vii e;
vi adj[N];

struct dsu
{
       int fat[N];
       int cnt[N] ;
       int comp = 0;
       dsu()
       {
              fill(cnt , cnt + N , 1) ;
              iota(fat, fat + N, 0);
       }
       void link(int u, int v)
       {
              u = find(u);
              v = find(v);
              if(u != v){
                     ++ comp ; 
                     cnt[v] += cnt[u] ; 
                     cnt[u] = 0 ; 
                     fat[u] = v; 
              }
       }

       int find(int x)
       {
              return fat[x] = x == fat[x] ? x : find(fat[x]);
       }

} d1, d2;

bool bad(int x ,int y){
       int flag = 0 ; 
       for(auto u: adj[x]){
              if(u != y){
                     flag|=1 ;
                     break;
              }
       }
       for(auto u: adj[y]){
              if(u != x){
                     flag|=2 ; 
                     break;
              }
       }
       return flag == 3 ;
}

int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);
#ifndef ONLINE_JUDGE
#endif
       cin >> n >> m;
       for (int i = 0; i < m; ++i)
       {
              int u, v;
              char c;
              cin >> u >> v >> c;
              if (c == 'T')
              {
                     d1.link(u, v);
              }
              else
              {
                     e.pb({u, v});
              }
              d2.link(u, v);
       }

       if (d2.comp != n - 1)
              return cout << 0, 0;

       int ans = 0;  


       if (e.empty())
       {
              return cout << n, 0;
       }
       else
       {
              for (auto u : e)
              {
                     int v1 = d1.find(u.f);
                     int v2 = d1.find(u.s);
                     if (v1 != v2)
                     {
                            adj[v1].pb(v2);
                            adj[v2].pb(v1);
                     }
              }
              for(int i =1 ;i <= n;++ i){
                     sort(all(adj[i])) ; 
                     adj[i].erase(unique(all(adj[i])) , adj[i].end()) ;
              }
              int ac = n - d1.comp ;

              for(int i = 1;i <= n;++ i){
                     if(sz(adj[i]) == ac - 1){
                            ans += d1.cnt[ i ] ;
                     }
              }
              cout << ans ;
       }

       return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 91 ms 11756 KB Execution killed with signal 11

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4204 KB Output is correct
2 Correct 3 ms 4204 KB Output is correct
3 Correct 4 ms 4332 KB Output is correct
4 Correct 6 ms 4460 KB Output is correct
5 Correct 4 ms 4204 KB Output is correct
6 Correct 144 ms 15320 KB Output is correct
7 Runtime error 80 ms 16108 KB Execution killed with signal 11

Subtask #3
30.0 / 30.0

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

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4204 KB Output is correct
2 Correct 3 ms 4204 KB Output is correct
3 Correct 4 ms 4332 KB Output is correct
4 Correct 5 ms 4460 KB Output is correct
5 Correct 6 ms 4588 KB Output is correct
6 Correct 5 ms 4460 KB Output is correct
7 Correct 3 ms 4204 KB Output is correct
8 Correct 3 ms 4204 KB Output is correct
9 Correct 7 ms 4588 KB Output is correct
10 Correct 4 ms 4204 KB Output is correct
11 Correct 4 ms 4332 KB Output is correct
12 Correct 3 ms 4204 KB Output is correct
13 Correct 4 ms 4332 KB Output is correct
14 Correct 4 ms 4332 KB Output is correct
15 Correct 4 ms 4332 KB Output is correct
16 Correct 4 ms 4204 KB Output is correct
17 Correct 4 ms 4204 KB Output is correct
18 Correct 3 ms 4204 KB Output is correct
19 Correct 4 ms 4332 KB Output is correct
20 Correct 6 ms 4460 KB Output is correct
21 Correct 4 ms 4204 KB Output is correct
22 Correct 15 ms 5232 KB Output is correct
23 Correct 126 ms 15456 KB Output is correct
24 Correct 55 ms 8800 KB Output is correct
25 Correct 69 ms 10336 KB Output is correct
26 Correct 39 ms 7784 KB Output is correct
27 Correct 62 ms 9056 KB Output is correct
28 Correct 9 ms 5100 KB Output is correct
29 Correct 15 ms 5360 KB Output is correct
30 Correct 49 ms 6636 KB Output is correct

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4204 KB Output is correct
2 Correct 3 ms 4204 KB Output is correct
3 Correct 4 ms 4332 KB Output is correct
4 Correct 5 ms 4460 KB Output is correct
5 Correct 6 ms 4588 KB Output is correct
6 Correct 5 ms 4460 KB Output is correct
7 Correct 3 ms 4204 KB Output is correct
8 Correct 3 ms 4204 KB Output is correct
9 Correct 7 ms 4588 KB Output is correct
10 Correct 4 ms 4204 KB Output is correct
11 Correct 4 ms 4332 KB Output is correct
12 Correct 3 ms 4204 KB Output is correct
13 Correct 4 ms 4332 KB Output is correct
14 Correct 4 ms 4332 KB Output is correct
15 Correct 4 ms 4332 KB Output is correct
16 Correct 15 ms 5232 KB Output is correct
17 Correct 126 ms 15456 KB Output is correct
18 Correct 55 ms 8800 KB Output is correct
19 Correct 69 ms 10336 KB Output is correct
20 Correct 39 ms 7784 KB Output is correct
21 Correct 62 ms 9056 KB Output is correct
22 Runtime error 91 ms 11756 KB Execution killed with signal 11