oj.uz

Submission #39957

# Submission time Handle Problem Language Result Execution time Memory
39957 2018-01-25T03:50:55 Z funcsr Space Pirate (JOI14_space_pirate) C++14
10 / 100
 2000 ms 61784 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 1145141919

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

int main() {
  cin >> N >> K;
  if (N > 3000) abort();
  rep(i, N) cin >> A[i], A[i]--;
  int def_dst = f(0, K);
  rep(a, N) {
    rep(b, N) {
      int orig = A[a];
      A[a] = b;
      rep(i, N) 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;
        int x = i;
        rep(_, N) {
          dist[i][x] = min(dist[i][x], _);
          x = A[x];
        }
      }
      C[f(0, K)]++;
      A[a] = orig;
    }
  }
  rep(i, N) cout << C[i] << "\n";
  return 0;
}

Compilation message

space_pirate.cpp: In function 'int main()':
space_pirate.cpp:33:7: warning: unused variable 'def_dst' [-Wunused-variable]
   int def_dst = f(0, K);
       ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 61784 KB Output is correct
2 Correct 362 ms 61784 KB Output is correct
3 Correct 352 ms 61784 KB Output is correct
4 Correct 349 ms 61784 KB Output is correct
5 Correct 351 ms 61784 KB Output is correct
6 Correct 353 ms 61784 KB Output is correct
7 Correct 360 ms 61784 KB Output is correct
8 Correct 355 ms 61784 KB Output is correct
9 Correct 377 ms 61784 KB Output is correct
10 Correct 402 ms 61784 KB Output is correct
11 Correct 394 ms 61784 KB Output is correct
12 Correct 368 ms 61784 KB Output is correct
13 Correct 361 ms 61784 KB Output is correct
14 Correct 396 ms 61784 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 61784 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 61784 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 61784 KB Execution killed because of forbidden syscall gettid (186)
2 Halted 0 ms 0 KB -