Submission #1696275


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]++;
    }
  }
};

// カウンター
template <typename T>
struct Counter {
  map<T, ull> cnt;
  void add(T key) {
    if (cnt.count(key)) {
      cnt[key]++;
    } else {
      cnt[key] = 1;
    }
  }
  ll get(T key) {
    if (cnt.count(key)) {
      return cnt[key];
    } else {
      return 0;
    }
  }
  typename map<T, ll>::iterator begin() {
    return cnt.begin();
  }
  typename map<T, ll>::iterator end() {
    return cnt.end();
  }
  typename map<T, ll>::reverse_iterator rbegin() {
    return cnt.rbegin();
  }
  typename map<T, ll>::reverse_iterator rend() {
    return cnt.rend();
  }
};

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);
  }

  Counter<pair<int, int>> c;
  for (int i = 0; i < N; i++) {
    c.add(make_pair(road.par[i], train.par[i]));
  }

  for (int i = 0; i < N; i++) {
    cout << c.get(make_pair(road.par[i], train.par[i]));
    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 2517 Byte
Status WA
Exec Time 231 ms
Memory 15104 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 3
AC × 6
WA × 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 28 ms 256 KB
subtask1_1.txt WA 231 ms 15104 KB
subtask1_10.txt AC 29 ms 384 KB
subtask1_11.txt WA 205 ms 13440 KB
subtask1_12.txt WA 101 ms 12928 KB
subtask1_13.txt WA 109 ms 14208 KB
subtask1_14.txt WA 106 ms 11136 KB
subtask1_2.txt WA 84 ms 9856 KB
subtask1_3.txt WA 113 ms 14208 KB
subtask1_4.txt WA 109 ms 12032 KB
subtask1_5.txt AC 30 ms 384 KB
subtask1_6.txt WA 193 ms 12672 KB
subtask1_7.txt WA 106 ms 14208 KB
subtask1_8.txt WA 116 ms 14336 KB
subtask1_9.txt WA 94 ms 8832 KB