Submission #465659

#	Time	Username	Problem	Language	Result	Execution time	Memory
465659		alexxela12345	Keys (IOI21_keys)	C++17	37 / 100	3084 ms	28116 KiB

keys

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

int n;
vector<vector<pair<int, int>>> g;
map<int, vector<pair<int, int>>> byColor;
vector<int> r;

int calcp(int st) {
  vector<int> used(n);
  set<int> keys;
  used[st] = 1;
  keys.insert(r[st]);
  deque<pair<int, int>> evs;
  evs.push_back({0, st});
  while (!evs.empty()) {
    if (evs.front().first == 0) {
      int v = evs.front().second;
      for (auto [u, c] : g[v]) {
	if (keys.count(c) && !used[u]) {
	  used[u] = 1;
	  evs.push_back({0, u});
	  if (!keys.count(r[u])) {
	    evs.push_back({1, r[u]});
	    keys.insert(r[u]);
	  }
	}
      }
    } else {
      int c = evs.front().second;
      for (auto [u, v] : byColor[c]) {
	if (used[u] || used[v]) {
	  if (!used[u]) {
	    used[u] = 1;
	    evs.push_back({0, u});
	    if (!keys.count(r[u])) {
	      evs.push_back({1, r[u]});
	      keys.insert(r[u]);
	    }
	  }
	  if (!used[v]) {
	    used[v] = 1;
            evs.push_back({0, v});
	    if (!keys.count(r[v])) {
	      evs.push_back({1, r[v]});
	      keys.insert(r[v]);
	    }
          }
        }
      }
    }
    evs.pop_front();
  }
  return accumulate(used.begin(), used.end(), 0);
}

vector<int> getp() {
  vector<int> p(n);
  for (int i = 0; i < n; i++) {
    p[i] = calcp(i);
  }
  return p;
}

vector<int> find_reachable(vector<int> r_, vector<int> u, vector<int> v,
			   vector<int> c) {
  r = r_;
  n = r.size();
  g.clear();
  g.resize(n);
  int m = u.size();
  for (int i = 0; i < m; i++) {
    g[u[i]].push_back({v[i], c[i]});
    g[v[i]].push_back({u[i], c[i]});
    byColor[c[i]].push_back({u[i], v[i]});
  }
  vector<int> p = getp();
  int mn = *min_element(p.begin(), p.end());
  vector<int> ans(r.size());
  for (int i = 0; i < (int)p.size(); i++) {
    if (p[i] == mn)
      ans[i] = 1;
  }
  return ans;
}

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