Submission #1155779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155779		abczz	Lockpicking (IOI23_lockpicking)	C++20	100 / 100	1 ms	328 KiB

lockpicking

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

using namespace std;


void construct_card(int N, std::vector<int> A, std::vector<std::vector<int>> S);
void define_states(int M, std::vector<int> B, std::vector<std::vector<int>> T, int j0);

map <ll, ll> mp, mp2;
vector <int> A;
vector <vector<int>> S;
vector <int> X;
vector <vector <int>> Y;
ll visited[150];
ll cur = 0;

void dfs(ll u) {
  if (visited[u] != -1) return;
  visited[u] = X.size();
  X.push_back(A[u]);
  Y.push_back({-1, -1});
  if (visited[S[u][A[u]]] != -1) Y[Y.size()-1][A[u]] = visited[S[u][A[u]]];
  else Y[Y.size()-1][A[u]] = X.size();
  dfs(S[u][A[u]]);
}

void advance(ll u, ll v, ll w) {
  if (w == 155) return;
  if (A[u] == X[v]) {
    advance(S[u][X[v]], Y[v][A[u]], w+1);
    return;
  }
  ++mp2[S[u][X[v]]];
}
void construct_card(int N, std::vector<int> in, std::vector<std::vector<int>> in2) {
  mp.clear(); mp2.clear();
  swap(in, A);
  swap(in2, S);
  for (int i=0; i<N; ++i) ++mp[i];
	while (!mp.empty()) {
    int i = mp.begin()->first;
    cur = X.size();
    for (int j=0; j<N; ++j) visited[j] = -1;
    dfs(i);
    if (mp.size() != 1) {
      auto it = next(mp.begin());
      while (it != mp.end()) {
        advance(it->first, cur, 0);
        it = next(it);
      }
    }
    for (int j=cur; j<X.size(); ++j) {
      if (Y[j][0] == -1) Y[j][0] = X.size();
      else Y[j][1] = X.size();
    }
    swap(mp, mp2);
    mp2.clear();
  }
  X.push_back(0);
  Y.push_back({0, 0});
  define_states(X.size(), X, Y, 0);
}

• Subtask 1: 21 / 21
• Subtask 2: 30 / 30
• Subtask 3: 20 / 20
• Subtask 4: 29 / 29