Submission #125752

#	Time	Username	Problem	Language	Result	Execution time	Memory
125752		AngusRitossa	Space Pirate (JOI14_space_pirate)	C++14	47 / 100	1686 ms	91256 KiB

space_pirate

#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 + n*sz;
		for (int j = 0; j <= n; j++)
		{
			if (!at[i][j]) continue;
			ans[from[i][(dis-j)%sz+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]);
                               ~~~~~^~~~~~~~~~~~~

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