oj.uz

Submission #218229

# Submission time Handle Problem Language Result Execution time Memory
218229 2020-04-01T15:05:15 Z Haunted_Cpp Monthly railway pass (LMIO18_menesinis_bilietas) C++17
65 / 100
 3000 ms 41976 KB 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <cassert>
#include <string>
#include <cstring>
#include <bitset>
#include <random>
#include <chrono>
 
#define FOR(i, a, b) for(int i = a; i < (int) b; i++)
#define F0R(i, a) FOR (i, 0, a)
#define ROF(i, a, b) for(int i = a; i >= (int) b; i--)
#define R0F(i, a) ROF(i, a, 0)
#define GO(i, a) for (auto i : a)
 
#define rsz resize
#define eb emplace_back
#define pb push_back
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define f first
#define s second
 
using namespace std;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vpii> vvpii;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef vector<pi64> vpi64;

const int dr[] = {+1, -1, +0, +0, +1, -1, +1, -1};
const int dc[] = {+0, +0, +1, -1, +1, -1, -1, +1};
const int ms[] = {+31, +29, +31, 30, +31, +30, +31, +31, +30, +31, +30, +31};

const int N = 5e5 + 5;

vvi g (N);
vvi bus (N);
vi color (N, -1);

bool vis [N], valid_color [N];
int group = 0;

void dfs (int node) {
  vis[node] = true;
  color[node] = group;
  GO (to, g[node]) {
    if (!vis[to]) {
      vis[to] = true;
      dfs (to);
    }
  }
}

bitset<N> unique_color;

void solve (int node) {
  vis[node] = true;
  unique_color.set(color[node]);
  GO (to, bus[node]) {
    unique_color.set(color[to]);
  }
  GO (to, g[node]) {
    if (!vis[to]) {
      vis[to] = true;
      solve (to);
    }
  }
}

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  F0R (i, m) {
    char tipo;
    int st, et;
    cin >> st >> et >> tipo;
    --st; --et;
    if (tipo == 'T') {
      g[st].eb(et);
      g[et].eb(st);
    } else {
      bus[st].eb(et);
      bus[et].eb(st);
    }
  }
  F0R (i, n) {
    if (!vis[i]) {
      dfs (i);
      ++group;
    }
  }
  int res = 0;
  memset (vis, 0, sizeof(vis));
  F0R (i, n) {
    if (!vis[i]) {
      unique_color.reset();
      solve (i);
      if (unique_color.count() == group) valid_color[color[i]] = true;
    }
  }
  F0R (i, n) {
    if (valid_color[color[i]]) ++res;
  }
  cout << res << '\n';
  return 0;
}

Compilation message

menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:115:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (unique_color.count() == group) valid_color[color[i]] = true;
           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 41976 KB Output is correct
2 Correct 19 ms 26368 KB Output is correct
3 Correct 21 ms 26368 KB Output is correct
4 Execution timed out 3078 ms 26368 KB Time limit exceeded

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3078 ms 26368 KB Time limit exceeded

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 26368 KB Output is correct
2 Correct 18 ms 26368 KB Output is correct
3 Correct 19 ms 26496 KB Output is correct
4 Correct 20 ms 26496 KB Output is correct
5 Correct 22 ms 26624 KB Output is correct
6 Correct 21 ms 26496 KB Output is correct
7 Correct 22 ms 26368 KB Output is correct
8 Correct 19 ms 26368 KB Output is correct
9 Correct 25 ms 26624 KB Output is correct
10 Correct 18 ms 26368 KB Output is correct
11 Correct 22 ms 26452 KB Output is correct
12 Correct 29 ms 26368 KB Output is correct
13 Correct 20 ms 26368 KB Output is correct
14 Correct 19 ms 26368 KB Output is correct
15 Correct 25 ms 26496 KB Output is correct
16 Correct 19 ms 26368 KB Output is correct
17 Correct 21 ms 26368 KB Output is correct
18 Correct 18 ms 26368 KB Output is correct
19 Correct 20 ms 26368 KB Output is correct
20 Correct 43 ms 26496 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 26368 KB Output is correct
2 Correct 18 ms 26368 KB Output is correct
3 Correct 19 ms 26496 KB Output is correct
4 Correct 20 ms 26496 KB Output is correct
5 Correct 22 ms 26624 KB Output is correct
6 Correct 21 ms 26496 KB Output is correct
7 Correct 22 ms 26368 KB Output is correct
8 Correct 19 ms 26368 KB Output is correct
9 Correct 25 ms 26624 KB Output is correct
10 Correct 18 ms 26368 KB Output is correct
11 Correct 22 ms 26452 KB Output is correct
12 Correct 29 ms 26368 KB Output is correct
13 Correct 20 ms 26368 KB Output is correct
14 Correct 19 ms 26368 KB Output is correct
15 Correct 25 ms 26496 KB Output is correct
16 Correct 26 ms 27136 KB Output is correct
17 Correct 136 ms 32376 KB Output is correct
18 Correct 69 ms 29176 KB Output is correct
19 Correct 68 ms 29560 KB Output is correct
20 Correct 43 ms 28536 KB Output is correct
21 Correct 98 ms 29688 KB Output is correct
22 Correct 19 ms 26368 KB Output is correct
23 Correct 21 ms 26368 KB Output is correct
24 Correct 18 ms 26368 KB Output is correct
25 Correct 20 ms 26368 KB Output is correct
26 Correct 43 ms 26496 KB Output is correct
27 Correct 319 ms 26400 KB Output is correct
28 Correct 365 ms 27000 KB Output is correct
29 Correct 393 ms 27384 KB Output is correct
30 Correct 72 ms 29688 KB Output is correct

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 26368 KB Output is correct
2 Correct 18 ms 26368 KB Output is correct
3 Correct 19 ms 26496 KB Output is correct
4 Correct 20 ms 26496 KB Output is correct
5 Correct 22 ms 26624 KB Output is correct
6 Correct 21 ms 26496 KB Output is correct
7 Correct 22 ms 26368 KB Output is correct
8 Correct 19 ms 26368 KB Output is correct
9 Correct 25 ms 26624 KB Output is correct
10 Correct 18 ms 26368 KB Output is correct
11 Correct 22 ms 26452 KB Output is correct
12 Correct 29 ms 26368 KB Output is correct
13 Correct 20 ms 26368 KB Output is correct
14 Correct 19 ms 26368 KB Output is correct
15 Correct 25 ms 26496 KB Output is correct
16 Correct 26 ms 27136 KB Output is correct
17 Correct 136 ms 32376 KB Output is correct
18 Correct 69 ms 29176 KB Output is correct
19 Correct 68 ms 29560 KB Output is correct
20 Correct 43 ms 28536 KB Output is correct
21 Correct 98 ms 29688 KB Output is correct
22 Correct 427 ms 41976 KB Output is correct
23 Correct 19 ms 26368 KB Output is correct
24 Correct 21 ms 26368 KB Output is correct
25 Execution timed out 3078 ms 26368 KB Time limit exceeded