Submission #126702

#	Time	Username	Problem	Language	Result	Execution time	Memory
126702		fizzydavid	Space Pirate (JOI14_space_pirate)	C++14	0 / 100	869 ms	72740 KiB

space_pirate

//by yjz
#include<bits/stdc++.h>
#define FF first
#define SS second
#define MP make_pair
#define PB push_back
typedef long long ll;
using namespace std;
const int maxn = 100111;
int n, a[maxn], L;
ll K;
int go[60][maxn];
ll ans[maxn];
vector<int> route;
int rid[maxn], T;
bool on_route[maxn];
ll lz[60][maxn];
void add(int x, ll m, ll v)
{
	for (int i=59; i>=0; i--)
	{
		if (m>=(1ll<<i))
		{
			lz[i][x] += v;
			m -= 1<<i;
			x = go[i][x];
		}
	}
}
void add_lazy(int x, ll l, ll r, ll v)
{
//	cerr<<"add_lazy:"<<x<<" "<<l<<","<<r<<" "<<v<<endl;
	add(x, r, v);
	add(x, l-1, -v);
}
void dfs(int x, ll l)
{
	if (!l||on_route[x]) return;
	on_route[x] = true;
	rid[x] = route.size();
	route.PB(x);
	dfs(a[x], l-1);
}
void after_work()
{
	for (int i=59; i>=0; i--)
	{
		for (int x=1; x<=n; x++)
		{
			if (i>0)
			{
				lz[i-1][x] += lz[i][x];
				lz[i-1][go[i-1][x]] += lz[i][x];
			}
			else
			{
				ans[x] += lz[0][x];
			}
		}
	}
}
int main()
{
	scanf("%d%lld", &n, &K);
	for (int i=1; i<=n; i++) scanf("%d", &a[i]), go[0][i] = a[i];
	dfs(1, K);
	for (int i=1; i<60; i++) for (int j=1; j<=n; j++) go[i][j] = go[i-1][go[i-1][j]];
	T = 1;
	for (int i=0; i<60; i++) if ((K>>i)&1) T = go[i][T];
	L = route.size();

	//a is not in route
	{
		int cnt = 0;
		for (int i=1; i<=n; i++) cnt += !on_route[i];
		ans[T] += 1ll*cnt*n;
	}
//	for (int i=1; i<=n; i++) printf("%lld\n", ans[i]);
	//a is in route, b is not in route
	{
		for (int i=1; i<=n; i++)
		{
			if (!on_route[i])
			{
				add_lazy(i, K-L, K-1, 1);
			}
		}
	}
	//a is in route, b is in route
	{
		for (int i=1; i<=L; i++)
		{
			int c = K%i;
			int lst = i-2;
			for (int k=0; k*i+c<L; k++)
			{
				int r = min(L-1, k*i+i-1+c);
				ans[route[k*i+c]] += r-lst;
				lst = r;
			}
			/*
			for (int j=i-1; j<L; j++)
			{
				ans[route[((j-c)/i)*i+c]]++;
			}
			*/
		}
		for (int i=0; i<L; i++)
		{
			int c = K%(L-i);
			ans[route[c]] += max(0, L-(c+i+1));
			ans[route[c+i]] += L-i-1-max(0, L-(c+i+1));
		}
	}
//	for (int i=1; i<=n; i++) printf("%lld\n", ans[i]);
	after_work();
	for (int i=1; i<=n; i++) printf("%lld\n", ans[i]);
	return 0;
}

/*
5 7
5 1 4 3 2
*/

Compilation message (stderr)

space_pirate.cpp: In function 'int main()':
space_pirate.cpp:64: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:65:45: 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]), go[0][i] = a[i];
                           ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

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