提出 #11023532


ソースコード 拡げる

Copy
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

struct UnionFind {
  std::vector<int> parent;
  int __size;
  UnionFind(int size_) : parent(size_, -1), __size(size_) {}
  void unite(int x, int y) {
    if ((x = root(x)) != (y = root(y))) {
      if (parent[y] < parent[x]) std::swap(x, y);
      parent[x] += parent[y];
      parent[y] = x;
      __size--;
    }
  }
  bool same(int x, int y) { return root(x) == root(y); }
  int root(int x) { return parent[x] < 0 ? x : parent[x] = root(parent[x]); }
  int size(int x) { return -parent[root(x)]; }
  int size() { return __size; }
};

int main() {
  int n, k, l;
  cin >> n >> k >> l;

  UnionFind uf1(n);
  for (int i = 0; i < k; i++) {
    int a, b; cin >> a >> b;
    uf1.unite(a-1, b-1);
  }

  UnionFind uf2(n);
  for (int i = 0; i < l; i++) {
    int a, b; cin >> a >> b;
    uf2.unite(a-1, b-1);
  }

  map<pair<int, int>, int> mp;
  for (int i = 0; i < n; i++) {
    mp[make_pair(uf1.root(i), uf2.root(i))]++;
  }

  for (int i = 0; i < n; i++) {
    cout << mp[make_pair(uf1.root(i), uf2.root(i))];
    cout << (i == n-1 ? "\n" : " ");
  }

  return 0;
}

提出情報

提出日時
問題 D - 連結
ユーザ kira924age
言語 C++14 (GCC 5.4.1)
得点 400
コード長 1214 Byte
結果
実行時間 213 ms
メモリ 13568 KB

ジャッジ結果

セット名 得点 / 配点 テストケース
Sample 0 / 0 subtask0_0.txt, subtask0_1.txt, subtask0_2.txt
All 400 / 400 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
ケース名 結果 実行時間 メモリ
subtask0_0.txt 1 ms 256 KB
subtask0_1.txt 1 ms 256 KB
subtask0_2.txt 1 ms 256 KB
subtask1_0.txt 86 ms 256 KB
subtask1_1.txt 213 ms 13568 KB
subtask1_10.txt 88 ms 256 KB
subtask1_11.txt 198 ms 12160 KB
subtask1_12.txt 141 ms 11520 KB
subtask1_13.txt 157 ms 12672 KB
subtask1_14.txt 164 ms 8832 KB
subtask1_2.txt 126 ms 8704 KB
subtask1_3.txt 158 ms 12544 KB
subtask1_4.txt 165 ms 9728 KB
subtask1_5.txt 90 ms 256 KB
subtask1_6.txt 190 ms 11392 KB
subtask1_7.txt 145 ms 12672 KB
subtask1_8.txt 166 ms 12672 KB
subtask1_9.txt 154 ms 6400 KB