oj.uz

Submission #39961

# Submission time Handle Problem Language Result Execution time Memory
39961 2018-01-25T04:07:27 Z funcsr Space Pirate (JOI14_space_pirate) C++14
47 / 100
 1862 ms 96964 KB 
#include <iostream>
#include <queue>
#include <cassert>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y) - x.begin())
#define pb push_back
#define _1 first
#define _2 second
//#define INF (1LL<<60)
#define INF 1145141919

int N;
long long K;
int A[100000];
int F[60][100000];
long long C[100000];
int dist[3000][3000];
int dst[3000][3001], len[3000];
inline int f(int x, long long k) {
  if (k <= N) return dst[x][k];
  k -= N;
  x = dst[x][N];
  return dst[x][k%len[x]];
  //for (int i=59; i>=0; i--) if ((k>>i)&1) x = F[i][x];
  //return x;
}

signed main() {
  cin >> N >> K;
  if (N > 3000) abort();
  rep(i, N) cin >> A[i], A[i]--, F[0][i] = A[i];
  rep(i, 59) rep(j, N) F[i+1][j] = F[i][F[i][j]];
  rep(i, N) {
    rep(j, N) dist[i][j] = INF;
    len[i] = INF;
    int x = i;
    rep(_, N+1) {
      dist[i][x] = min(dist[i][x], _);
      dst[i][_] = x;
      if (_ > 0 && x == i) len[i] = min(len[i], _);
      x = A[x];
    }
  }
  int def_dst = f(0, K);
  rep(a, N) {
    int d = dist[0][a];
    if (d == INF || K <= d) {
      C[def_dst] += N;
      continue;
    }
    long long K2 = K-d;
    rep(b, N) {
      if (dist[b][a] == INF) {
        C[f(b, K2-1)]++;
      }
      else {
        int len = 1+dist[b][a];
        long long s = K2%len;
        if (s == 0) C[a]++;
        else C[dst[b][s-1]]++;
      }
    }
  }
  rep(i, N) cout << C[i] << "\n";
  return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 96964 KB Output is correct
2 Correct 30 ms 96964 KB Output is correct
3 Correct 90 ms 96964 KB Output is correct
4 Correct 1862 ms 96964 KB Output is correct
5 Correct 999 ms 96964 KB Output is correct
6 Correct 939 ms 96964 KB Output is correct
7 Correct 1629 ms 96964 KB Output is correct
8 Correct 692 ms 96964 KB Output is correct
9 Correct 1353 ms 96964 KB Output is correct
10 Correct 605 ms 96964 KB Output is correct
11 Correct 37 ms 96964 KB Output is correct
12 Correct 1761 ms 96964 KB Output is correct
13 Correct 631 ms 96964 KB Output is correct
14 Correct 759 ms 96964 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 96964 KB Execution killed because of forbidden syscall gettid (186)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 96964 KB Execution killed because of forbidden syscall gettid (186)
2 Halted 0 ms 0 KB -