Submission #1139740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139740		DariusH	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	10 / 100	303 ms	66036 KiB

menesinis_bilietas

#include <bits/stdc++.h>

using namespace std;

//ifstream fin("input.in");
//ofstream fout("output.out");

#define N_MAX 500001
vector<int> gf_bus[N_MAX];
vector<int> gf_train[N_MAX];

set<int> gf_group[N_MAX];

int group[N_MAX], group_length[N_MAX];

void dfs_train(int pos, int gr) {
  int i;
  group[pos] = gr;
  ++group_length[gr];

  for(i = 0; i < (int)gf_train[pos].size(); ++i) {
    if(group[ gf_train[pos][i] ] == 0) {
      dfs_train(gf_train[pos][i], gr);
    }
  }
}

int main()
{
  int n, m, i, j, a, b, cnt;
  char ch;
  cin >> n >> m;
  for(i = 0; i < m; ++i) {
    cin >> a >> b >> ch;
    --a, --b;
    if(ch == 'T') {
      gf_train[a].push_back(b);
      gf_train[b].push_back(a);
    }else{
      gf_bus[a].push_back(b);
      gf_bus[b].push_back(a);
    }
  }

  cnt = 1;
  for(i = 0; i < n; ++i) {
    if(group[i] == 0) {
      dfs_train(i, cnt++);
    }
  }

  for(i = 0; i < n; ++i) {
    for(j = 0; j < (int)gf_bus[i].size(); ++j) {
      if(group[i] != group[j]) {
        gf_group[group[i]].insert( group[gf_bus[i][j]] );
        gf_group[ group[gf_bus[i][j]] ].insert(group[i]);
      }
    }
  }

  int rz = 0;
  for(i = 1; i <= cnt; ++i) {
    if( gf_group[i].size() == cnt - 2 ) {
      rz += group_length[i];
    }
  }

  cout << rz << '\n';

  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 6
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35
• Subtask 5: 0 / 19