Submission #1696259


Source Code Expand

#include <assert.h>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>
#include <numeric>
#include <functional>
#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <bitset>
typedef long long ll;
typedef unsigned long long ull;

using namespace std;

template <typename T>
struct UnionFind {
  vector<T> par;
  vector<T> rank;

  explicit UnionFind(int n) {
    par = vector<T>(n, 0);
    iota(par.begin(), par.end(), 0);
    rank = vector<T>(n, 0);
  }
  // 木の根を求める
  T root(T x) {
    if (par[x] ==x) {
      return x;
    } else {
      return par[x] = root(par[x]);
    }
  }
  // x と y が同じ集合に属するか調べる
  bool same(T x, T y) {
    return root(x) == root(y);
  }
  // x と y が属する集合を併合する
  void unite(T x, T y) {
    x = root(x);
    y = root(y);
    if (x == y) return;
    if (rank[x] < rank[y]) {
      par[x] = y;
    } else {
      par[y] = x;
      if (rank[x] == rank[y]) rank[x]++;
    }
  }
};

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N, K, L;
  cin >> N >> K >> L;

  UnionFind<int> road(N);
  UnionFind<int> train(N);

  for (int i = 0; i < K; i++) {
    int p, q;
    cin >> p >> q;
    p--;
    q--;
    road.unite(p, q);
  }

  for (int i = 0; i < L; i++) {
    int r, s;
    cin >> r >> s;
    r--;
    s--;
    train.unite(r, s);
  }

  for (int i = 0; i < N; i++) {
    int c = 0;
    for (int j = 0; j < N; j++) {
      if (road.same(i, j) && train.same(i, j)) {
        c++;
      }
    }
    cout << c;
    if (i < N - 1) {
      cout << " ";
    }
  }
  cout << endl;
  return 0;
}

Submission Info

Submission Time
Task D - Connectivity
User sinhrks
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1868 Byte
Status TLE
Exec Time 2103 ms
Memory 3328 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 3
AC × 6
TLE × 12
Set Name Test Cases
Sample subtask0_0.txt, subtask0_1.txt, subtask0_2.txt
All subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt
Case Name Status Exec Time Memory
subtask0_0.txt AC 1 ms 256 KB
subtask0_1.txt AC 1 ms 256 KB
subtask0_2.txt AC 1 ms 256 KB
subtask1_0.txt AC 61 ms 256 KB
subtask1_1.txt TLE 2103 ms 3328 KB
subtask1_10.txt AC 76 ms 384 KB
subtask1_11.txt TLE 2103 ms 2944 KB
subtask1_12.txt TLE 2103 ms 3072 KB
subtask1_13.txt TLE 2103 ms 3328 KB
subtask1_14.txt TLE 2103 ms 2688 KB
subtask1_2.txt TLE 2103 ms 2560 KB
subtask1_3.txt TLE 2103 ms 3328 KB
subtask1_4.txt TLE 2103 ms 2816 KB
subtask1_5.txt AC 86 ms 384 KB
subtask1_6.txt TLE 2103 ms 2816 KB
subtask1_7.txt TLE 2103 ms 3328 KB
subtask1_8.txt TLE 2103 ms 3328 KB
subtask1_9.txt TLE 2103 ms 2304 KB