oj.uz

Submission #258682

# Submission time Handle Problem Language Result Execution time Memory
258682 2020-08-06T11:05:43 Z fedoseevtimofey Space Pirate (JOI14_space_pirate) C++14
47 / 100
 1305 ms 213112 KB 
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>

using namespace std;

typedef long long ll;

const int N = 3007;
const int K = 60;

int go[K][N];
int slow_go[N][4 * N];
ll min_dist[N][N];
int cycle_len[N];
bool used[N];

int big_step(ll x) {
  return 63 - __builtin_clzll(x);
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n; ll k;
  cin >> n >> k;
  vector <int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    --a[i];
  }
  for (int i = 0; i < n; ++i) {
    go[0][i] = a[i];
  }
  for (int i = 1; i < K; ++i) {
    for (int j = 0; j < n; ++j) {
      go[i][j] = go[i - 1][go[i - 1][j]];
    }
  }
  for (int i = 0; i < n; ++i) {
    int u = go[K - 1][i];
    if (used[u]) continue;
    int len = 1;
    int v = a[u];
    while (v != u) {
      v = a[v];
      ++len;
    }
    used[u] = 1;
    cycle_len[u] = len;
    v = a[u];
    while (v != u) {
      used[v] = 1;
      cycle_len[v] = len;
      v = a[v];
    }
  }
  auto get = [&] (int u, ll x) {
    if (x <= 4 * n) return slow_go[u][x];
    int p2 = big_step(x);
    u = go[p2][u];
    x -= (1LL << p2);
    x %= cycle_len[u];
    u = slow_go[u][x];
    return u;
  };

  for (int i = 0; i < n; ++i) {
    slow_go[i][0] = i;
    slow_go[i][1] = a[i];
    for (int j = 2; j <= 4 * n; ++j) {
      slow_go[i][j] = a[slow_go[i][j - 1]];
    }
  }
  int gogo = get(0, k);
  const ll Inf = 2e18;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      min_dist[i][j] = Inf;
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= n; ++j) {
      min_dist[i][slow_go[i][j]] = min(min_dist[i][slow_go[i][j]], (ll)j);
    }
  }   
  vector <int> cnt(n);
  for (int x = 0; x < n; ++x) {
    for (int y = 0; y < n; ++y) {
      ll cur_k = 0;
      int u = 0;
      if (min_dist[u][x] > (k - cur_k)) {
        ++cnt[gogo];
        continue;
      }
      cur_k = min_dist[u][x];
      u = x;
      if (cur_k < k && u == x) {
        u = y;
        ++cur_k;
      }
      if (min_dist[u][x] > (k - cur_k)) {
        ++cnt[get(u, k - cur_k)];
        continue;
      }
      ll cycle_len = min_dist[u][x];
      cur_k += min_dist[u][x];
      u = x;
      if (cur_k < k && u == x) {
        ++cur_k;
        ++cycle_len;
        u = y;
      }
      if (cur_k < k) {
        ll need = (k - cur_k) % cycle_len;
        u = get(u, need);
      }
      ++cnt[u];
    }
  }
  for (int i = 0; i < n; ++i) {
    cout << cnt[i] << '\n';
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1664 KB Output is correct
2 Correct 1 ms 1664 KB Output is correct
3 Correct 1 ms 1664 KB Output is correct
4 Correct 1 ms 1664 KB Output is correct
5 Correct 1 ms 1664 KB Output is correct
6 Correct 1 ms 1664 KB Output is correct
7 Correct 1 ms 1664 KB Output is correct
8 Correct 1 ms 1664 KB Output is correct
9 Correct 1 ms 1664 KB Output is correct
10 Correct 1 ms 1664 KB Output is correct
11 Correct 1 ms 1664 KB Output is correct
12 Correct 1 ms 1664 KB Output is correct
13 Correct 2 ms 1664 KB Output is correct
14 Correct 1 ms 1664 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1664 KB Output is correct
2 Correct 1 ms 1664 KB Output is correct
3 Correct 1 ms 1664 KB Output is correct
4 Correct 1 ms 1664 KB Output is correct
5 Correct 1 ms 1664 KB Output is correct
6 Correct 1 ms 1664 KB Output is correct
7 Correct 1 ms 1664 KB Output is correct
8 Correct 1 ms 1664 KB Output is correct
9 Correct 1 ms 1664 KB Output is correct
10 Correct 1 ms 1664 KB Output is correct
11 Correct 1 ms 1664 KB Output is correct
12 Correct 1 ms 1664 KB Output is correct
13 Correct 2 ms 1664 KB Output is correct
14 Correct 1 ms 1664 KB Output is correct
15 Correct 254 ms 213112 KB Output is correct
16 Correct 232 ms 212984 KB Output is correct
17 Correct 261 ms 212984 KB Output is correct
18 Correct 1305 ms 212920 KB Output is correct
19 Correct 832 ms 213040 KB Output is correct
20 Correct 720 ms 212860 KB Output is correct
21 Correct 1092 ms 212860 KB Output is correct
22 Correct 527 ms 212984 KB Output is correct
23 Correct 865 ms 212988 KB Output is correct
24 Correct 439 ms 212984 KB Output is correct
25 Correct 241 ms 212992 KB Output is correct
26 Correct 1231 ms 213000 KB Output is correct
27 Correct 489 ms 212988 KB Output is correct
28 Correct 601 ms 212856 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 2944 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1664 KB Output is correct
2 Correct 1 ms 1664 KB Output is correct
3 Correct 1 ms 1664 KB Output is correct
4 Correct 1 ms 1664 KB Output is correct
5 Correct 1 ms 1664 KB Output is correct
6 Correct 1 ms 1664 KB Output is correct
7 Correct 1 ms 1664 KB Output is correct
8 Correct 1 ms 1664 KB Output is correct
9 Correct 1 ms 1664 KB Output is correct
10 Correct 1 ms 1664 KB Output is correct
11 Correct 1 ms 1664 KB Output is correct
12 Correct 1 ms 1664 KB Output is correct
13 Correct 2 ms 1664 KB Output is correct
14 Correct 1 ms 1664 KB Output is correct
15 Correct 254 ms 213112 KB Output is correct
16 Correct 232 ms 212984 KB Output is correct
17 Correct 261 ms 212984 KB Output is correct
18 Correct 1305 ms 212920 KB Output is correct
19 Correct 832 ms 213040 KB Output is correct
20 Correct 720 ms 212860 KB Output is correct
21 Correct 1092 ms 212860 KB Output is correct
22 Correct 527 ms 212984 KB Output is correct
23 Correct 865 ms 212988 KB Output is correct
24 Correct 439 ms 212984 KB Output is correct
25 Correct 241 ms 212992 KB Output is correct
26 Correct 1231 ms 213000 KB Output is correct
27 Correct 489 ms 212988 KB Output is correct
28 Correct 601 ms 212856 KB Output is correct
29 Runtime error 24 ms 2944 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -