Submission #1228851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228851		rxlfd314	Keys (IOI21_keys)	C++17	20 / 100	3095 ms	23824 KiB

keys

#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

vt<int> find_reachable(vt<int> R, vt<int> U, vt<int> V, vt<int> C) {
  const int N = size(R), M = size(U);
  vt<vt<ari2>> adj(N);
  FOR(i, 0, M-1) {
    adj[U[i]].push_back({V[i], C[i]});
    adj[V[i]].push_back({U[i], C[i]});
  }
  vt<int> ret(N);
  int cur = N;
  FOR(root, 0, N-1) {
    vt<int> seen(N), have(N);
    vt<vt<int>> adj2(N);
    queue<int> qu;
    qu.push(root);
    seen[root] = 1;
    have[R[root]] = 1;
    while (size(qu)) {
      const int i = qu.front();
      qu.pop();
      for (const auto &[j, c] : adj[i])
        if (!seen[j])
          adj2[c].push_back(j);
      FOR(c, 0, N-1) {
        if (!have[c])
          continue;
        for (const auto &j : adj2[c])
          if (!seen[j]) {
            seen[j] = 1;
            have[R[j]] = 1;
            qu.push(j);
          }
      }
    }
    const int v = accumulate(all(seen), 0);
    if (v < cur) {
      cur = v;
      fill(all(ret), 0);
    }
    if (v == cur)
      ret[root] = 1;
  }
  return ret;
}

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