Submission #422726

#TimeUsernameProblemLanguageResultExecution timeMemory
422726ACmachineSpace Pirate (JOI14_space_pirate)C++17
0 / 100
267 ms524292 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l)) #define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l)) #define REP(i, n) FOR(i, 0, n, 1) #define REPD(i, n) FORD(i, n, 0, 1) #define pb push_back const int INF = (int)1e9; typedef long long ll; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n; ll k; cin >> n >> k; vector<int> g(n); REP(i, n){ cin >> g[i]; g[i]--; } vector<vector<int>> dist(n, vector<int>(n, -1)); vector<vector<int>> revdist(n, vector<int>(n, -1)); // who is at dist x? vector<int> maxdist(n); function<void(int, int, int)> dfs = [&](int v, int d, int s){ dist[s][v] = d; if(dist[s][g[v]] == -1){ dfs(g[v], d + 1, s); } }; REP(i, n){ dfs(i, 0, i); } REP(i, n){ REP(j, n){ if(dist[i][j] != -1) revdist[i][dist[i][j]] = j; } } REP(i, n){ maxdist[i] = *max_element(dist[i].begin(), dist[i].end()); } auto go = [&](int v, ll k){ // in default graph; k >= comp_size!!, otherwise doesn't work; if(maxdist[v] == 0) return v; ll kk = k - maxdist[v]; v = revdist[v][maxdist[v]]; int u = revdist[v][1]; ll cycle_size = 1 + dist[u][v]; kk %= cycle_size; if(kk == 0) return v; else return revdist[u][kk - 1]; }; vector<int> ans(n, 0); int def = go(0, k); REP(a, n){ REP(b, n){ if(dist[0][a] == -1){ // neviem sa dostat do zaciatku novej hrany ans[def]++; } else if(dist[b][a] == -1){ // nevytvorim cyklus ans[go(b, k - dist[0][a] - 1)]++; } else if(a == b){ // rovnake ans[a]++; } else{ // vytvorim cyklus; pojdem do a ll kk = k - dist[0][a]; ll cycle_size = 1 + dist[b][a]; kk %= cycle_size; if(kk == 0) ans[a]++; else ans[revdist[b][kk - 1]]++; } //cout << a << " " << b << " " << ans[0] << "\n"; } } REP(i, n){ cout << ans[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...