oj.uz

Submission #967396

# Submission time Handle Problem Language Result Execution time Memory
967396 2024-04-22T04:32:26 Z nguyentunglam Keys (IOI21_keys) C++17
20 / 100
 3000 ms 88632 KB 
#include <vector>
#include<bits/stdc++.h>
using namespace std;

const int N = 3e5 + 10;

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

priority_queue<pair<int, int> > waiting[N], 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];

  priority_queue<pair<int, int> > q;
  for(auto &[v, c] : adj[u]) q.push({h_keys[c], v});
  for(auto &[v, c] : adj[u]) waiting[c].push({h[u], v});

//
//  cout << h[reach(u)] << endl;
//  cout << q.top().first << endl;
//  if (u == 2) {
//    cout << q.size() << " " << waiting[r[u]].size() << "@" << endl;
//  }
  while (!q.empty() || !waiting[r[u]].empty()) {
    if (!q.empty() && q.top().first >= h[reach(u)]) {
      int depth, v; tie(depth, v) = q.top(); q.pop();
//      if (u == 1) {
//        cout << v << "#" << " " << vis[v] << endl;
//        climb(u, v);
//      }
      if (vis[v] == 0) {
        can_vis.push({h[u], v});
      }
      if (vis[v] == 1) {
        climb(u, v);
      }
      if (vis[v] == 2) {
        return;
      }
    }
    else if (!waiting[r[u]].empty() && waiting[r[u]].top().first >= h[reach(u)]) {
      int depth, v; tie(depth, v) = waiting[r[u]].top(); waiting[r[u]].pop();
      if (vis[v] == 0) {
        can_vis.push({h[u], v});
      }
      if (vis[v] == 1) {
        climb(u, v);
      }
      if (vis[v] == 2) {
        return;
      }
    }
    else break;
  }
//  if (u == 8) cout << reach(u) << "@" << endl;

  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]) {
        while (!waiting[c].empty()) waiting[c].pop();
      }
      while (!can_vis.empty()) can_vis.pop();
    } unfinished.clear();
    for(int i = 0; i < n; i++) {
      while (!waiting[i].empty()) waiting[i].pop();
    }
  }

	int mn = 1e9;

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

	assert(mn != 1e9);

  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

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:113:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for(int i = 0; i < U.size(); i++) {
      |                  ~~^~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25944 KB Output is correct
2 Correct 5 ms 25948 KB Output is correct
3 Correct 7 ms 25948 KB Output is correct
4 Correct 5 ms 25944 KB Output is correct
5 Correct 6 ms 25948 KB Output is correct
6 Correct 5 ms 25948 KB Output is correct
7 Correct 5 ms 25948 KB Output is correct
8 Correct 6 ms 25948 KB Output is correct
9 Correct 5 ms 25948 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25944 KB Output is correct
2 Correct 5 ms 25948 KB Output is correct
3 Correct 7 ms 25948 KB Output is correct
4 Correct 5 ms 25944 KB Output is correct
5 Correct 6 ms 25948 KB Output is correct
6 Correct 5 ms 25948 KB Output is correct
7 Correct 5 ms 25948 KB Output is correct
8 Correct 6 ms 25948 KB Output is correct
9 Correct 5 ms 25948 KB Output is correct
10 Correct 5 ms 25948 KB Output is correct
11 Correct 5 ms 25948 KB Output is correct
12 Correct 6 ms 26064 KB Output is correct
13 Correct 5 ms 25948 KB Output is correct
14 Correct 5 ms 25948 KB Output is correct
15 Correct 5 ms 26132 KB Output is correct
16 Correct 5 ms 25948 KB Output is correct
17 Correct 5 ms 25948 KB Output is correct
18 Correct 6 ms 25948 KB Output is correct
19 Correct 6 ms 25948 KB Output is correct
20 Correct 6 ms 25948 KB Output is correct
21 Correct 6 ms 25948 KB Output is correct
22 Correct 7 ms 25948 KB Output is correct
23 Correct 7 ms 25944 KB Output is correct
24 Correct 5 ms 25944 KB Output is correct
25 Correct 6 ms 25944 KB Output is correct
26 Correct 5 ms 25948 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25944 KB Output is correct
2 Correct 5 ms 25948 KB Output is correct
3 Correct 7 ms 25948 KB Output is correct
4 Correct 5 ms 25944 KB Output is correct
5 Correct 6 ms 25948 KB Output is correct
6 Correct 5 ms 25948 KB Output is correct
7 Correct 5 ms 25948 KB Output is correct
8 Correct 6 ms 25948 KB Output is correct
9 Correct 5 ms 25948 KB Output is correct
10 Correct 5 ms 25948 KB Output is correct
11 Correct 5 ms 25948 KB Output is correct
12 Correct 6 ms 26064 KB Output is correct
13 Correct 5 ms 25948 KB Output is correct
14 Correct 5 ms 25948 KB Output is correct
15 Correct 5 ms 26132 KB Output is correct
16 Correct 5 ms 25948 KB Output is correct
17 Correct 5 ms 25948 KB Output is correct
18 Correct 6 ms 25948 KB Output is correct
19 Correct 6 ms 25948 KB Output is correct
20 Correct 6 ms 25948 KB Output is correct
21 Correct 6 ms 25948 KB Output is correct
22 Correct 7 ms 25948 KB Output is correct
23 Correct 7 ms 25944 KB Output is correct
24 Correct 5 ms 25944 KB Output is correct
25 Correct 6 ms 25944 KB Output is correct
26 Correct 5 ms 25948 KB Output is correct
27 Correct 8 ms 26204 KB Output is correct
28 Correct 8 ms 26200 KB Output is correct
29 Correct 9 ms 26204 KB Output is correct
30 Correct 6 ms 26200 KB Output is correct
31 Correct 7 ms 26456 KB Output is correct
32 Incorrect 6 ms 26200 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25944 KB Output is correct
2 Correct 5 ms 25948 KB Output is correct
3 Correct 7 ms 25948 KB Output is correct
4 Correct 5 ms 25944 KB Output is correct
5 Correct 6 ms 25948 KB Output is correct
6 Correct 5 ms 25948 KB Output is correct
7 Correct 5 ms 25948 KB Output is correct
8 Correct 6 ms 25948 KB Output is correct
9 Correct 5 ms 25948 KB Output is correct
10 Correct 2366 ms 59964 KB Output is correct
11 Execution timed out 3048 ms 88632 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25944 KB Output is correct
2 Correct 5 ms 25948 KB Output is correct
3 Correct 7 ms 25948 KB Output is correct
4 Correct 5 ms 25944 KB Output is correct
5 Correct 6 ms 25948 KB Output is correct
6 Correct 5 ms 25948 KB Output is correct
7 Correct 5 ms 25948 KB Output is correct
8 Correct 6 ms 25948 KB Output is correct
9 Correct 5 ms 25948 KB Output is correct
10 Correct 5 ms 25948 KB Output is correct
11 Correct 5 ms 25948 KB Output is correct
12 Correct 6 ms 26064 KB Output is correct
13 Correct 5 ms 25948 KB Output is correct
14 Correct 5 ms 25948 KB Output is correct
15 Correct 5 ms 26132 KB Output is correct
16 Correct 5 ms 25948 KB Output is correct
17 Correct 5 ms 25948 KB Output is correct
18 Correct 6 ms 25948 KB Output is correct
19 Correct 6 ms 25948 KB Output is correct
20 Correct 6 ms 25948 KB Output is correct
21 Correct 6 ms 25948 KB Output is correct
22 Correct 7 ms 25948 KB Output is correct
23 Correct 7 ms 25944 KB Output is correct
24 Correct 5 ms 25944 KB Output is correct
25 Correct 6 ms 25944 KB Output is correct
26 Correct 5 ms 25948 KB Output is correct
27 Correct 8 ms 26204 KB Output is correct
28 Correct 8 ms 26200 KB Output is correct
29 Correct 9 ms 26204 KB Output is correct
30 Correct 6 ms 26200 KB Output is correct
31 Correct 7 ms 26456 KB Output is correct
32 Incorrect 6 ms 26200 KB Output isn't correct
33 Halted 0 ms 0 KB -