제출 #1084785

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1084785		abczz	열쇠 (IOI21_keys)	C++17	0 / 100	3081 ms	42588 KiB

keys

#include <vector>
#include <iostream>
#include <array>
#include <map>
#define ll long long

using namespace std;

ll n, m, f, cnt, A[300000], sz[300000], szout[300000], done[300000], P[300000];
vector <ll> V;
bool visited[300000];
map <ll, ll> keys[300000], edge[300000];
map <ll, vector<ll>> out[300000];

ll dsu(ll u) {
  if (P[u] == u) return u;
  else return P[u] = dsu(P[u]);
}

void merge(ll u, ll v) {
  if (edge[u].size() < edge[v].size()) {
    for (auto [x, y] : edge[u]) ++edge[v][dsu(x)];
    swap(edge[u], edge[v]);
  }
  else {
    for (auto [x, y] : edge[v]) ++edge[u][dsu(x)];
  }
  if (keys[u].size()+szout[v] < keys[v].size()+szout[u]) {
    for (auto [x, y] : keys[u]) {
      if (out[v].count(x)) {
        for (auto g : out[v][x]) ++edge[u][dsu(g)];
      }
      keys[v].insert({x, y});
    }
    swap(keys[u], keys[v]);
    for (auto [x, y] : out[v]) {
      if (keys[u].count(x)) {
        for (auto g : y) ++edge[u][dsu(g)];
      }
      else out[u].insert({x, y});
    }
  }
  else {
    for (auto [x, y] : keys[v]) {
      if (out[u].count(x)) {
        for (auto g : out[u][x]) ++edge[u][dsu(g)];
      }
      keys[u].insert({x, y});
    }
    for (auto [x, y] : out[u]) {
      if (keys[u].count(x)) {
        for (auto g : y) ++edge[u][dsu(g)];
      }
      else out[v].insert({x, y});
    }
    swap(out[u], out[v]);
  }
  if (edge[u].count(u)) edge[u].erase(u);
  if (edge[u].count(v)) edge[u].erase(v);
  if (edge[v].count(u)) edge[v].erase(u);
  if (edge[v].count(v)) edge[v].erase(v);
  sz[u] += sz[v];
  szout[u] += szout[v];
  P[v] = u;
}
void dfs(ll u) {
  done[u] = cnt;
  visited[u] = 1;
  V.push_back(u);
  auto it = edge[u].begin();
  while (it != edge[u].end()) {
    ll x = dsu(it->first);
    auto nx = next(it);
    if (u == x && done[x] > cnt) continue;
    if (visited[x]) {
      while (!V.empty() && V.back() != x) {
        auto v = dsu(V.back());
        V.pop_back();
        merge(x, v);
      }
    }
    if (done[x] == -1) {
      dfs(x);
    }
    it = nx;
  }
  visited[u] = 0;
  if (V.back() == dsu(u)) V.pop_back();
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	n = r.size(), m = u.size(), cnt = 0;
  for (int i=0; i<n; ++i) {
    P[i] = i;
    done[i] = -1;
    sz[i] = 1;
    ++keys[i][r[i]];
  }
  for (int i=0; i<m; ++i) {
    if (c[i] == r[u[i]]) ++edge[u[i]][v[i]];
    else out[u[i]][c[i]].push_back(v[i]), ++szout[u[i]];
    if (c[i] == r[v[i]]) ++edge[v[i]][u[i]];
    else out[v[i]][c[i]].push_back(u[i]), ++szout[v[i]];
  }
  vector <int> F(n, 0);
  bool ok = 0;
  for (int i=0; i<n; ++i) {
    if (edge[i].empty()) {
      F[i] = ok = 1;
    }
  }
  if (ok) return F;
  for (int i=0; i<n; ++i) {
    if (done[i] == -1) {
      dfs(i);
      ++cnt;
    }
  }
  ll f = 1e18;
  for (int i=0; i<n; ++i) {
    auto x = dsu(i);
    if (edge[x].empty()) f = min(f, sz[x]);
  }
  for (int i=0; i<n; ++i) {
    auto x = dsu(i);
    if (edge[x].empty() && sz[x] == f) F[i] = 1;
    else F[i] = 0;
  }
  return F;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33