Submission #1084924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084924		abczz	Keys (IOI21_keys)	C++17	0 / 100	3046 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> 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[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]);
  }
  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);
  //cout << u << endl;
  for (auto [z, y] : edge[u]) {
    ll x = dsu(z);
    if (dsu(u) == x || (done[x] != -1 && done[x] != cnt)) continue;
    if (visited[x]) {
      while (!V.empty() && V.back() != x) {
        auto v = dsu(V.back());
        V.pop_back();
        merge(x, v);
        //cout << v << " ";
      }
      //cout << x << endl;
    }
    if (done[x] == -1) {
      //cout << u << "->" << x << endl;
      dfs(x);
    }
  }
  visited[u] = 0;
  if (!V.empty() && 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;
  mp.clear();
  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) {
    ++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);
    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