oj.uz

Submission #967384

# Submission time Handle Problem Language Result Execution time Memory
967384 2024-04-22T03:56:36 Z nguyentunglam Keys (IOI21_keys) C++17
9 / 100
 274 ms 91444 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) {
    if (find_nxt(u) == u) return u;
    return nxt[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 (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;
//    cerr << q.size() << " " << waiting[r[u]].size() << endl;
//    cout << endl;
  }
//  cout << can_vis.size() << endl;

  while (!can_vis.empty()) {
    int depth, v; tie(depth, v) = can_vis.top();
//    cerr << depth << " " << v << endl;
    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;
  }
//  if (u == 2) return;

//  if (u == 2) cout << pre[u] << " " << reach(u) << " " << nxt[find_nxt(2)] << endl;
//  if (u == 2) return;
  int v = reach(u);
  int cost = h[u] - h[v] + 1;
  while (1) {
//    cerr << v << endl;
    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();
//    break;
  }

//	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

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

Subtask #1
9.0 / 9.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 17756 KB Output is correct
2 Correct 5 ms 17756 KB Output is correct
3 Correct 5 ms 17752 KB Output is correct
4 Correct 7 ms 17756 KB Output is correct
5 Correct 5 ms 17752 KB Output is correct
6 Correct 6 ms 17756 KB Output is correct
7 Correct 6 ms 16928 KB Output is correct
8 Correct 6 ms 17756 KB Output is correct
9 Correct 6 ms 17756 KB Output is correct
10 Correct 6 ms 17756 KB Output is correct
11 Correct 6 ms 17756 KB Output is correct
12 Correct 7 ms 16732 KB Output is correct
13 Correct 7 ms 16924 KB Output is correct
14 Correct 7 ms 16984 KB Output is correct
15 Correct 7 ms 16732 KB Output is correct
16 Correct 7 ms 16728 KB Output is correct
17 Incorrect 7 ms 16728 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 17756 KB Output is correct
2 Correct 5 ms 17756 KB Output is correct
3 Correct 5 ms 17752 KB Output is correct
4 Correct 7 ms 17756 KB Output is correct
5 Correct 5 ms 17752 KB Output is correct
6 Correct 6 ms 17756 KB Output is correct
7 Correct 6 ms 16928 KB Output is correct
8 Correct 6 ms 17756 KB Output is correct
9 Correct 6 ms 17756 KB Output is correct
10 Correct 6 ms 17756 KB Output is correct
11 Correct 6 ms 17756 KB Output is correct
12 Correct 7 ms 16732 KB Output is correct
13 Correct 7 ms 16924 KB Output is correct
14 Correct 7 ms 16984 KB Output is correct
15 Correct 7 ms 16732 KB Output is correct
16 Correct 7 ms 16728 KB Output is correct
17 Incorrect 7 ms 16728 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 17756 KB Output is correct
2 Correct 5 ms 17756 KB Output is correct
3 Correct 5 ms 17752 KB Output is correct
4 Correct 7 ms 17756 KB Output is correct
5 Correct 5 ms 17752 KB Output is correct
6 Correct 6 ms 17756 KB Output is correct
7 Correct 6 ms 16928 KB Output is correct
8 Correct 6 ms 17756 KB Output is correct
9 Correct 6 ms 17756 KB Output is correct
10 Correct 218 ms 58056 KB Output is correct
11 Correct 274 ms 91444 KB Output is correct
12 Incorrect 38 ms 23380 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 17756 KB Output is correct
2 Correct 5 ms 17756 KB Output is correct
3 Correct 5 ms 17752 KB Output is correct
4 Correct 7 ms 17756 KB Output is correct
5 Correct 5 ms 17752 KB Output is correct
6 Correct 6 ms 17756 KB Output is correct
7 Correct 6 ms 16928 KB Output is correct
8 Correct 6 ms 17756 KB Output is correct
9 Correct 6 ms 17756 KB Output is correct
10 Correct 6 ms 17756 KB Output is correct
11 Correct 6 ms 17756 KB Output is correct
12 Correct 7 ms 16732 KB Output is correct
13 Correct 7 ms 16924 KB Output is correct
14 Correct 7 ms 16984 KB Output is correct
15 Correct 7 ms 16732 KB Output is correct
16 Correct 7 ms 16728 KB Output is correct
17 Incorrect 7 ms 16728 KB Output isn't correct
18 Halted 0 ms 0 KB -