Submission #723898

#	Time	Username	Problem	Language	Result	Execution time	Memory
723898		awu	Keys (IOI21_keys)	C++17	100 / 100	1227 ms	54336 KiB

keys

#include <bits/extc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

// #define int long long
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(x) do{auto __tmp__ = x; cerr << #x << " = " << __tmp__ << endl;}while(0)
// #define endl "\n"
#define unordered_map __gnu_pbds::gp_hash_table
using pii = pair<int, int>;

// const int inf = 1ll << 60;
const int inf = 1 << 30;
const int MOD = 1e9 + 7;

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
  srand(time(0));
  int n = r.size();
  int m = u.size();
  vector<vector<pii>> adj(n);
  for(int i = 0; i < m; i++) {
    adj[u[i]].push_back({v[i], c[i]});
    adj[v[i]].push_back({u[i], c[i]});
  }
  for(auto i : adj) {
    random_shuffle(all(i));
  }
  int best = n;
  vector<int> has(n, -1);
  vector<vector<int>> todo(n);
  vector<int> toclr;
  vector<int> vis(n, -1);
  vector<bool> done(n);
  vector<int> cnt(n, inf);
  function<void(int)> trial = [&](int x) {
    vector<int> visl;
    deque<int> q;
    q.push_back(x);
    while(q.size()) {
      auto cur = q[0]; q.pop_front();
      if(vis[cur] == x) continue;
      vis[cur] = x;
      visl.push_back(cur);
      if(visl.size() > best) return;
      if(has[r[cur]] != x) {
        has[r[cur]] = x;
        for(auto i : todo[r[cur]]) {
          if(done[i]) return;
          q.push_back(i);
        }
        todo[r[cur]].clear();
      }
      for(auto e : adj[cur]) {
        if(has[e.s] == x) {
          if(done[e.f]) return;
          q.push_back(e.f);
        } else {
          if(todo[e.s].empty()) {
            toclr.push_back(e.s);
          }
          todo[e.s].push_back(e.f);
        }
      }
    }
    best = visl.size();
    for(auto i : visl) {
      cnt[i] = min(cnt[i], (int)visl.size());
    }
  };
  vector<int> perm(n);
  iota(all(perm), 0);
  for(int i = 0; i < m; i++) {
    perm.push_back(u[i]);
    perm.push_back(v[i]);
  }
  random_shuffle(all(perm));
  for(auto i : perm) {
    if(done[i]) continue;
    trial(i);
    done[i] = true;
    for(auto j : toclr) {
      todo[j].clear();
    }
    toclr.clear();
  }
  vector<int> ans(n);
  for(int i = 0; i < n; i++) {
    if(cnt[i] == best) {
      ans[i] = 1;
    }
  }
  return ans;
}

// signed main() {
//   ios_base::sync_with_stdio(0);
//   cin.tie(0);
//   for(auto i : find_reachable({0, 1, 1, 2}, {0, 0, 1, 1, 3}, {1, 2, 2, 3, 1}, {0, 0, 1, 0, 2})) {
//     cout << i << " ";
//   }
//   cout << endl;
// }

Compilation message (stderr)

keys.cpp: In lambda function:
keys.cpp:48:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |       if(visl.size() > best) return;
      |          ~~~~~~~~~~~~^~~~~~

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