Submission #1085499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085499		abczz	Keys (IOI21_keys)	C++17	20 / 100	3025 ms	116820 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> mp, 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[u] < keys[v].size()+szout[v]) {
    for (auto [x, y] : keys[u]) {
      if (out[v].count(x)) {
        for (auto g : out[v][x]) ++edge[u][dsu(g)];
        out[v].erase(x);
      }
      keys[v].insert({x, y});
    }
    swap(keys[u], keys[v]);
    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]);
  }
  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[v]) {
      if (keys[u].count(x)) {
        for (auto g : y) ++edge[u][dsu(g)];
      }
      else out[u].insert({x, y});
    }
  }
  sz[u] += sz[v];
  szout[u] += szout[v];
  P[v] = u;
}

ll dfs(ll u) {
  done[u] = cnt;
  visited[u] = 1;
  for (auto it = edge[u].begin(); it != edge[u].end();) {
    auto nx = next(it);
    ll v = dsu(it->first), x;
    edge[u].erase(it);
    if (v == u || done[v] < cnt) {
      it = nx;
      if (done[v] < cnt) sz[u] += sz[v];
      continue;
    }
    if (visited[v]) return v;
    while (true) {
      x = dfs(v);
      if (x != -2) break;
    }
    if (x != -1) {
      merge(u, v);
      if (x == u) return -2;
      return x;
    }
    else sz[u] += sz[v];
    it = nx;
  }
  visited[u] = 0;
  return -1;
}

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;
  mp.clear();
  for (int i=0; i<n; ++i) {
    P[i] = i;
    done[i] = 1e18;
    sz[i] = 1;
    szout[i] = 0;
    ++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);
  for (int i=0; i<n; ++i) {
    if (done[i] == 1e18) {
      ll x;
      while (true) {
        x = dfs(i);
        if (x != -2) break;
      }
      ++cnt;
    }
  }
  ll f = 1e18;
  for (int i=0; i<n; ++i) {
    ++mp[dsu(i)];
  }
  for (auto [x, y] : mp) {
    for (auto it = edge[x].begin(); it != edge[x].end();) {
      auto nx = next(it);
      ll z = dsu(it->first);
      if (x == z) edge[x].erase(it);
      it = nx;
    }
  }
  for (int i=0; i<n; ++i) {
    auto x = dsu(i);
    f = min(f, sz[x]);
  }
  for (int i=0; i<n; ++i) {
    auto x = dsu(i);
    if (sz[x] == f) F[i] = 1;
    else F[i] = 0;
  }
  return F;
}

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