Submission #258665

#TimeUsernameProblemLanguageResultExecution timeMemory
258665fedoseevtimofeySpace Pirate (JOI14_space_pirate)C++14
10 / 100
2096 ms107136 KiB
#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][N]; ll min_dist[N][N]; 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]]; } } auto get = [&] (int u, ll x) { if (x <= n) return slow_go[u][x]; for (int i = K - 1; i >= 0; --i) { if (x & (1LL << i)) { u = go[i][u]; } } return u; }; int gogo = get(0, k); for (int i = 0; i < n; ++i) { slow_go[i][0] = i; slow_go[i][1] = a[i]; for (int j = 2; j <= n; ++j) { slow_go[i][j] = a[slow_go[i][j - 1]]; } } 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'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...