Submission #967427

#	Time	Username	Problem	Language	Result	Execution time	Memory
967427		nguyentunglam	Keys (IOI21_keys)	C++17	100 / 100	446 ms	92276 KiB

keys

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

const int N = 3e5 + 10;

vector<pair<int, int> > adj[N];

vector<pair<int, int> > waiting[N];

priority_queue<pair<int, int> > q, can_vis;

int off[N], pre[N], nxt[N], h[N], h_keys[N], p[N], r[N], vis[N];

vector<int> unfinished;

int find_nxt (int i) {
  return off[i] == 0 ? i : pre[i] = find_nxt(pre[i]);
}

void calc (int u) {
//  cout << u << endl;
  vis[u] = 1;
  p[u] = 1e9;
  unfinished.push_back(u);

  auto climb = [&] (int u, int v) {
    while (1) {
      int climb = find_nxt(u);
      if (h[climb] <= h[v]) break;
      off[climb] = 1;
    }
  };

  auto reach = [&] (int u) {
    return find_nxt(u);
  };

  h_keys[r[u]] = h[u];

  for(auto &[v, c] : adj[u]) {
    q.push({h_keys[c], v});
    waiting[c].emplace_back(h[u], v);
  }

  for(auto &[depth, v] : waiting[r[u]]) {
    q.push({depth, v});
  } waiting[r[u]].clear();

  while (!q.empty() && q.top().first >= h[reach(u)]) {
    int depth, v; tie(depth, v) = q.top(); q.pop();

    if (vis[v] == 0) {
      can_vis.push({h[u], v});
    }
    if (vis[v] == 1) {
      climb(u, v);
    }
    if (vis[v] == 2) {
      return;
    }
  }

  while (!can_vis.empty()) {
    int depth, v; tie(depth, v) = can_vis.top();
    if (vis[v] != 0) {
      can_vis.pop();
      continue;
    }
    if (depth >= h[reach(u)]) {
      can_vis.pop();
      nxt[u] = v;
      pre[v] = u;
      h[v] = h[u] + 1;
      calc(v);
      return;
    }
    else break;
  }


  int v = reach(u);
  int cost = h[u] - h[v] + 1;
  while (1) {
    p[v] = cost;
    if (u == v) return;
    v = nxt[v];
  }
}

std::vector<int> find_reachable(std::vector<int> R, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
  int n = R.size();
	vector<int> ans(n);
  for(int i = 0; i < n; i++) r[i] = R[i];
  for(int i = 0; i < U.size(); i++) {
    adj[U[i]].emplace_back(V[i], C[i]);
    adj[V[i]].emplace_back(U[i], C[i]);
  }

  for(int i = 0; i < n; i++) if (!vis[i]) {
    pre[i] = n;
    nxt[n] = i;
    h[i] = 1;
    calc(i);
    for(int &j : unfinished) {
      vis[j] = 2;
      h_keys[r[j]] = 0;
      for(auto &[v, c] : adj[j]) {
        waiting[c].clear();
      }
      while (!can_vis.empty()) can_vis.pop();
      while (!q.empty()) q.pop();
    } unfinished.clear();
//    cout << endl;
  }

//	for(int i = 0; i < n; i++) cout << p[i] << " "; cout << endl;

	int mn = 1e9;

	for(int i = 0; i < n; i++) mn = min(mn, p[i]);

  for(int i = 0; i < n; i++) ans[i] = p[i] == mn;

	return ans;
}

#ifdef ngu
int main() {
  freopen ("task.inp", "r", stdin);
  freopen ("task.out", "w", stdout);
    int n, m;
    assert(2 == scanf("%d%d", &n, &m));
    std::vector<int> r(n), u(m), v(m), c(m);
    for(int i=0; i<n; i++) {
        assert(1 == scanf("%d", &r[i]));
    }
    for(int i=0; i<m; i++) {
        assert(3 == scanf("%d %d %d", &u[i], &v[i], &c[i]));
    }
    fclose(stdin);

    std::vector<int> ans = find_reachable(r, u, v, c);

    for (int i = 0; i < (int) ans.size(); ++i) {
        if(i) putchar(' ');
        putchar(ans[i]+'0');
    }
    printf("\n");
    return 0;
}
#endif // ngu

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:95:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |   for(int i = 0; i < U.size(); i++) {
      |                  ~~^~~~~~~~~~

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