Submission #649157

#	Time	Username	Problem	Language	Result	Execution time	Memory
649157		youngyojun	Space Pirate (JOI14_space_pirate)	C++17	47 / 100	347 ms	1248 KiB

space_pirate

#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define findx(V,x) (int(find(allv(V),(x))-(V).begin()))
#define erasex(V,x) (V).erase(find(allv(V),(x)))
using namespace std;
typedef long long ll;

const int MAXN = 3005;

vector<int> G[MAXN];

vector<int> CV[MAXN];
int Cn;

int D[MAXN];
bitset<MAXN> inTree, chk;

int A[MAXN];

ll Ans[MAXN];

ll K;
int N;

void dfs(vector<int> &cnt, int i, int j, int L, int CL, ll K) {
	cnt[(j+K-L)%CL]++;
	for(int v : G[i])
		dfs(cnt, v, j, L+1, CL, K);
}

void dfsTree(vector<int> &V, int i, int L, ll K) {
	chk[i] = true;
	V.eb(i); L++;
	Ans[V[(L - K%L)%L]]++;
	
	for(int v : G[i])
		dfsTree(V, v, L, K);
	
	V.pop_back();
}

void solve_naive(int R, ll K) {
	for(int i = N; i; i--) G[i].clear();
	for(int i = N; i; i--)
		if(i != R) G[A[i]].eb(i);
	chk.reset();
{
	vector<int> V;
	dfsTree(V, R, 0, K);
}
	
	for(int i = N; i; i--) if(!chk[i]) {
		vector<int> V;
		int j = i;
		while(!chk[j]) {
			chk[j] = true;
			V.eb(j);
			j = A[j];
		}
		int x = findx(V, j);
		if(sz(V) <= x) continue;
		
		CV[Cn++] = vector<int>(V.begin()+x, V.end());
	}
	
	for(int i = Cn; i--;) {
		int L = sz(CV[i]);
		vector<int> cnt(L, 0);
		for(int j = L; j--;)
			erasex(G[CV[i][j]], CV[i][(L+j-1)%L]);
		for(int j = L; j--;)
			dfs(cnt, CV[i][j], j, 0, L, K-1);
		for(int j = L; j--;)
			Ans[CV[i][j]] += cnt[j];
	}
	
	for(int i = Cn; i--;) CV[i].clear();
	Cn = 0;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> N >> K;
	for(int i = 1; i <= N; i++) cin >> A[i];
	
	vector<int> V;
	int L;
	
{
	int i = 1;
	while(!chk[i]) {
		chk[i] = true;
		V.eb(i);
		i = A[i];
	}
	L = sz(V) - findx(V, i);
}
	
	const int W = V[sz(V) - L + (K - (sz(V) - L)) % L];
	Ans[W] += ll(N - sz(V)) * N;
	
	for(int i = sz(V); i--;)
		solve_naive(V[i], K - i);

	for(int i = 1; i <= N; i++)
		cout << Ans[i] << '\n';
	
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 37 / 37
• Subtask 3: 0 / 33
• Subtask 4: 0 / 20