Submission #125751

#TimeUsernameProblemLanguageResultExecution timeMemory
125751AngusRitossaSpace Pirate (JOI14_space_pirate)C++14
47 / 100
1883 ms91384 KiB
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG #define D(x...) printf(x) #else #define D(x...) #endif typedef long long ll; int n, a[3010], ans[3010]; int canreach[3010][3010], at[3010][3010]; int from[3010][3030], fromsz[3010]; void dfs(int i, int j, int dis = 1) { while (!canreach[i][j]) { canreach[i][j] = dis++; from[i][fromsz[i]++] = j; j = a[j]; } } ll k; int main() { scanf("%d%lld", &n, &k); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n; i++) dfs(i, i); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (canreach[1][i]) { if (i == j) ans[i]++; else if (canreach[j][i]) { ll dis = k-canreach[1][i]+1; dis %= canreach[j][i]; int endpoint = i; if (dis > 0) endpoint = from[j][dis-1]; ans[endpoint]++; } else at[j][canreach[1][i]]++; } else at[1][0]++; } } for (int i = 1; i <= n; i++) { int cyclestart = a[from[i][fromsz[i]-1]]; int loc = -1; for (int j = 0; j < fromsz[i]; j++) { if (from[i][j] == cyclestart) { loc = j; break; } } assert(loc != -1); int sz = fromsz[i]-loc; ll dis2 = k-loc; int dis = dis2%sz; for (int j = 0; j <= n; j++) { if (!at[i][j]) continue; int d = dis-(ll)j; d += n*sz; d %= sz; ans[from[i][d+loc]] += at[i][j]; } } for (int i = 1; i <= n; i++) printf("%d\n", ans[i]); }

Compilation message (stderr)

space_pirate.cpp: In function 'int main()':
space_pirate.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~
space_pirate.cpp:25:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
                               ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...