Submission #1039372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039372		spacewalker	Keys (IOI21_keys)	C++17	9 / 100	1102 ms	180480 KiB

keys

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


template<class T, class U>
ostream& operator<< (ostream& os, const pair<T, U> &pair) {
  return os << '(' << pair.first << ", " << pair.second << ')';
}

template<class T>
ostream& operator<< (ostream& os, const vector<T> &arr) {
  os << '[';
  for (const T &v : arr) os << v << ", ";
  return os << ']';
}
// return a partial partition of {0, ..., n-1} corresponding to sccs that cannot reach any other nodes
vector<vector<int>> partial_sccs(const vector<int> &keys, const vector<vector<pair<int, int>>> &graph) {
  int n = keys.size();

  vector<vector<int>> ans;
  // finalized[i] = can this vtx currently reach a vtx in ans?
  vector<bool> finalized(n);

  vector<int> cstack;
  vector<int> stack_pos(n, -1);
  vector<int> lowest_on_stack(n, -1);
  // INVARIANT: If we haven't finalized this, every node on the stack
  // can reach some higher up node.
  
  vector<vector<int>> next_vertex_queue(n);
  vector<vector<pair<int, int>>> pending_color_queue(n);

  auto mark_vertex = [&] (int c) {
    for (auto &[from, to] : pending_color_queue[c]) {
      next_vertex_queue[from].push_back(to);
    }
    pending_color_queue[c].clear();
  };

  auto register_edge = [&] (int from, int to, int c) {
    pending_color_queue[c].emplace_back(from, to); 
  };

  function<bool(int)> visit; visit = [&] (int i) { // return value: is this not finalized yet?
    if (finalized[i]) return false;
    stack_pos[i] = cstack.size();
    cstack.push_back(i);
    lowest_on_stack[keys[i]] = stack_pos[i];
    int highest_stack_point = n; // WE WILL SET THIS LATER!
    // need to find edges to traverse, to update highest_stack_point, and to make recursive calls

    /*
    cerr << "visit " << i << endl;
    cerr << cstack << endl;
    cerr << stack_pos << endl;
    cerr << lowest_on_stack << endl;
    */
    mark_vertex(keys[i]);

    vector<pair<int, int>> neighbors = graph[i];
    for (auto [to, c] : neighbors) register_edge(i, to, c);
    sort(begin(neighbors), end(neighbors), [&] (pair<int, int> a, pair<int, int> b) {
        return lowest_on_stack[a.second] < lowest_on_stack[b.second];
    });
    // cerr << neighbors << endl;

    auto update_hsp = [&] (int stack_point) {
      highest_stack_point = min(highest_stack_point, stack_point);
      while (!neighbors.empty() && lowest_on_stack[neighbors.back().second] >= highest_stack_point) {
        next_vertex_queue[i].push_back(neighbors.back().first);
        neighbors.pop_back();
      }
    };

    auto traverse_edge = [&] (int to) {
      if (stack_pos[to] != -1) {
        update_hsp(stack_pos[to]);
        return true;
      } else {
        return visit(to);
      }
    };

    update_hsp(stack_pos[i]);
    while (!next_vertex_queue[i].empty()) {
      int v = next_vertex_queue[i].back(); next_vertex_queue[i].pop_back();
      if (!traverse_edge(v)) return false;
    }
    // cerr << "visit " << i << " end HSP " << highest_stack_point << endl;
    if (highest_stack_point >= stack_pos[i]) {
      // we've found a new SCC, add to the answer.
      // we will clean up later, for now, mark all vtxs here as finalized
      ans.emplace_back(begin(cstack) + stack_pos[i], end(cstack));
      for (int v : cstack) finalized[v] = true;
      // cerr << "added " << ans.back() << endl;
      return false;
    } else {
      return true;
    }
  };

  for (int i = 0; i < n; ++i) {
    if (!finalized[i]) {
      visit(i);
      // cerr << "visit finalized" << endl;
      // clean up the stack
      for (int v : cstack) {
        stack_pos[v] = -1;
        lowest_on_stack[keys[v]] = -1;
      }
      cstack.clear();
    }
  }

  return ans;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
  int n = r.size(), m = u.size();
  vector<vector<pair<int, int>>> graph(n);
  for (int i = 0; i < m; ++i) {
    graph[u[i]].emplace_back(v[i], c[i]);
    graph[v[i]].emplace_back(u[i], c[i]);
  }
  vector<vector<int>> sccs = partial_sccs(r, graph);
  int min_scc_size = n;
  for (auto &scc : sccs) min_scc_size = min((int)scc.size(), min_scc_size);
  vector<int> ans(n);
  for (auto &scc : sccs) {
    if (scc.size() == min_scc_size) {
      for (int v : scc) ans[v] = 1;
    }
  }
  return ans;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:130:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  130 |     if (scc.size() == min_scc_size) {
      |         ~~~~~~~~~~~^~~~~~~~~~~~~~~

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