Submission #234106

#	Time	Username	Problem	Language	Result	Execution time	Memory
234106		Nightlight	Monthly railway pass (LMIO18_menesinis_bilietas)	C++14	100 / 100	524 ms	40184 KiB

menesinis_bilietas

#include <bits/stdc++.h>
#define pii pair<int, bool>
using namespace std;

int N, M;
vector<pii> adj[500005];
int waktu;
int col[500005], col_sz[500005];
bool vis[500005];

void DFS(int u) {
  col[u] = waktu;
  col_sz[waktu]++;
  vis[u] = 1;
  for(pii now : adj[u]) {
    if(now.second == 1 || vis[now.first] == 1) continue;
    DFS(now.first);
  }
}

bool ketemu[500005];
int neigh[500005], p;
int cnt;

void DFS2(int u) {
  vis[u] = 1;
  for(pii now : adj[u]) {
    if(col[u] != col[now.first]) {
      if(ketemu[col[now.first]] == 0) {
        neigh[++p] = col[now.first];
        ketemu[col[now.first]] = 1;
        cnt += col_sz[col[now.first]];
      }
      continue;
    }
    if(vis[now.first] == 1) continue;
    DFS2(now.first);
  }
}

int ans;

void solve() {
  memset(vis, 0, sizeof(vis));
  for(int i = 1; i <= N; i++) {
    if(vis[i]) continue;
    DFS2(i);
//    cout << col[i] << " -> " << cnt << "\n";
    if(cnt + col_sz[col[i]] == N) {
      ans += col_sz[col[i]];
    }
    cnt = 0;
    for(int i = 1; i <= p; i++) {
      ketemu[neigh[i]] = 0;
    }
    p = 0;
  }
  printf("%d\n", ans);
}

int main() {
  scanf("%d %d", &N, &M);
  int u, v;
  char ty;
  for(int i = 1; i <= M; i++) {
    scanf("%d %d %c", &u, &v, &ty);
    adj[u].emplace_back(v, ty == 'A');
    adj[v].emplace_back(u, ty == 'A');
  }
  for(int i = 1; i <= N; i++) {
    if(vis[i]) continue;
    waktu++;
    DFS(i);
  }/*
  for(int i = 1; i <= N; i++) {
    cout << col[i] << " ";
  }
  cout << "\n";
  for(int i = 1; i <= waktu; i++) {
    cout << col_sz[i] << " ";
  }
  cout << "\n";*/
  solve();
  cin >> N;
}

Compilation message (stderr)

menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &N, &M);
   ~~~~~^~~~~~~~~~~~~~~~~
menesinis_bilietas.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %c", &u, &v, &ty);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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