Submission #1224896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224896		arashmemar	Space Pirate (JOI14_space_pirate)	C++20	80 / 100	2097 ms	73704 KiB

space_pirate

#include <bits/stdc++.h>
using namespace std;

const long long int maxn = 1e5 + 100;
long long int n;
long long int k;

bool mark1[maxn], markl[maxn], isc[maxn];
long long int nxt[maxn], hms, h[maxn], cl, vu[maxn], cycid[maxn], lp, dist[maxn], htl[maxn];

long long int ans[maxn], dif[maxn];

vector <long long int> divs[maxn * 2], ne[maxn];

queue <long long int> bfs;
long long int dis[maxn], id[maxn], csv;

struct Node
{
	long long int f[2 * maxn];
	vector <pair <long long int, long long int>> h;
	bool add;
	void init()
	{
		for (long long int i = 0;i < 2 * maxn;i++)
		{
			f[i] = 0;
		}
		h.clear();
		add = 1;
	}

	void update(long long int p, long long int v)
	{
		if (p == 0)
		{
			return ;
		}
		if (add)
		{
			h.push_back({p, v});
		}
		while (p < 2 * maxn)
		{
			f[p] += v;
			p += (p & -p);
		}
		return ;
	}

	long long int get(long long int p)
	{
		long long int ret = 0;
		while (p > 0)
		{
			ret += f[p];
			p -= (p & -p);
		}
		return ret;
	}

	long long int get(long long int l, long long int r)
	{
		return get(r - 1) - get(l - 1);
	}

	void clear()
	{
		add = 0;
		for (auto o : h)
		{
			update(o.first, -o.second);
		}
		h.clear();
		add = 1;
		return ;
	}
};

Node fr, nocl, sr;

void init(long long int v)
{
	vu[v] = 1;
	for (auto u : ne[v])
	{
		htl[u] = htl[v] + 1;
		init(u);
		vu[v] += vu[u];
	}
	return ;
}

void upd(long long int v, long long int h)
{
	nocl.update(htl[v] + 1, 1);
	nocl.update(htl[v] + cycid[v], -1);
	fr.update(h + hms, 1);
	for (auto u : ne[v])
	{
		upd(u, h + 1);
	}
	return ;
}

void fdfs(long long int v)
{
	if (ne[v].size() == 0)
	{
		hms = n;
		fr.clear();
		fr.update(hms, 1);
		nocl.clear();
		nocl.update(htl[v] + 1, 1);
		nocl.update(htl[v] + cycid[v], -1);
	}
	else
	{
		pair <long long int, long long int> mx = {0, 0};
		for (auto u : ne[v])
		{
			mx = max(mx, {vu[u], u});
		}
		for (auto u : ne[v])
		{
			if (u != mx.second)
			{
				fdfs(u);
			}
		}
		fdfs(mx.second);
		hms--;
		for (auto u : ne[v])
		{
			if (u != mx.second)
			{
				upd(u, 1);
			}
		}
		fr.update(hms, 1);
		nocl.update(htl[v] + 1, 1);
		nocl.update(htl[v] + cycid[v], -1);
	}

	long long int cn = k + dist[v] - id[v] + 1;
	for (auto len : divs[cn - k + n])
	{
		long long int minb = max(0ll, len - 1 - dist[v] - (cl + lp - id[v]));
		long long int maxb = len - 1 - dist[v];
		ans[v] += fr.get(minb + hms, maxb + hms + 1);

		//sdfsdfsdfsdf

		if (isc[v])
		{
			ans[v] -= nocl.get(len);
		}

		//sdfsdfjlsjflsdkfj
	}
	if (cycid[v] != 1 and !isc[v])
	{
		cn = k - lp + dis[v] + (cl + 1 - cycid[v]);
		for (auto len : divs[cn - k + n])
		{
			long long int minb = max(0ll, len - 1 - dis[v] - (cl - 1));
			long long int maxb = len - 1 - dis[v] - (cl + 1 - cycid[v]);
			ans[v] += fr.get(minb + hms, maxb + hms + 1);
		}
	}

	//yal be jolo ke agabesh bashe

	if (isc[v] and cycid[v] != 1)
	{
		cn = k - lp + dis[v] + (cl + 1 - cycid[v]);
		for (auto len : divs[cn - k + n])
		{
			ans[v] += nocl.get(len);
		}
	}
	return ;
}

void filli(long long int v)
{
	vu[v] = 1;
	mark1[v] = 1;
	for (auto u : ne[v])
	{
		if (mark1[u])
		{
			continue;
		}
		if (cycid[u] == 0)
		{
			cycid[u] = cycid[v];
		}
		if (dist[u] == -1)
		{
			dist[u] = dist[v] + 1;
		}
		filli(u);
		vu[v] += vu[u];
	}
	return ;
}

pair <long long int, long long int> f(long long int v)
{
	long long int nom = 0;
	long long int cur = v;
	while (mark1[cur] == 0)
	{
		mark1[cur] = 1;
		cur = nxt[cur];
	}
	long long int ret = cur;
	do
	{
		nom++;
		cur = nxt[cur];
	}while (cur != ret);
	

	while (mark1[v])
	{
		dist[v] = 0;
		mark1[v] = 0;
		v = nxt[v];
	}
	return {ret, nom};
}

void upd2(long long int v)
{
	sr.update(htl[v], 1);
	for (auto u : ne[v])
	{
		upd2(u);
	}
	return ;
}

void ldfs(long long int v)
{
	markl[v] = 1;
	if (nxt[v] != csv)
	{
		ldfs(nxt[v]);
	}
	long long int cn = k + dist[v] - id[v] + 1;
	for (auto len : divs[cn - k + n])
	{
		ans[v] += nocl.get(len);
		ans[v] -= sr.get(len - 1) - sr.get(len - cycid[v]);
	}
	for (auto u : ne[v])
	{
		if (markl[u])
		{
			continue;
		}
		upd2(u);
	}
	sr.update(htl[v], 1);
}

int main()
//void solve()
{
//	ifstream cin("in.in");
//	ofstream cout("out.out");

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;

	for (long long int i = 1;i <= n;i++)
	{
		dist[i] = -1;
	}

	for (long long int i = 1;i <= n;i++)
	{
		long long int tmp = (k - n + i - 1)	/ i;
		for (long long int j = tmp * i;j <= k + n;j += i)
		{
			divs[j - k + n].push_back(i);
		}
	}

	for (long long int i = 1;i <= n;i++)
	{
		cin >> nxt[i];
		ne[nxt[i]].push_back(i);
	}

	pair <long long int, long long int> tmp = f(1);
	long long int v = tmp.first, l = tmp.second;

	csv = v;
	cl = l;

	lp = 0;
	long long int cur = 1;
	while (cur != v)
	{
		cur = nxt[cur];
		lp++;
		l++;
	}

	long long int temp = k - lp;
	
	cur = v;
	while (temp % (l - lp))
	{
		temp--;
		cur = nxt[cur];
	}

	long long int sv = cur;


	tmp = f(1);
	v = tmp.first, l = tmp.second;

	cur = v;
	long long int ccycid = 1;
	while (nxt[cur] != v)
	{
		cycid[cur] = ccycid++;
		isc[cur] = 1;
		cur = nxt[cur];
	}
	isc[cur] = 1;
	cycid[cur] = ccycid;

	filli(cur);

	for (long long int i = 1;i <= n;i++)
	{
		if (mark1[i])
		{
			continue;
		}

		tmp = f(i);
		v = tmp.first;
		long long int ll = tmp.second;
		cur = v;
		long long int cid = 1;

		vector <long long int> c = {0}, dp = {0};

		do
		{
			ans[sv] += n;
			mark1[cur] = 1;
			bfs.push(cur);
			c.push_back(cur);
			dp.push_back(0);
			ans[cur] += l + lp;
			id[cur] = cid++;
			cur = nxt[cur];
		}while (cur != v);

		dp.push_back(0);

		while (bfs.size())
		{
			long long int v = bfs.front();
			bfs.pop();
			for (auto u : ne[v])
			{
				if (mark1[u])
				{
					continue;
				}
				mark1[u] = 1;
				dis[u] = dis[v] + 1;
				id[u] = id[v];
				bfs.push(u);

				dp[0] += ((l + lp) - 1) / ll;

				long long int st = id[u] + ((k - l - lp - dis[u]) % ll);
				st %= ll;
				if (st == 0)
				{
					st = ll;
				}
				long long int fn = st + l + lp - 1;
				fn %= ll;

				if (fn == 0)
				{
					fn = ll;
				}

				dp[st]++;
				dp[fn + 1]--;
				if (fn + 1 <= st)
				{
					dp[0]++;
				}
				ans[sv] += n;
			}
		}
		long long int pl = 0;
		for (long long int i = 0;i <= ll;i++)
		{
			pl += dp[i];
			ans[c[i]] += pl;
		}	
	}

	for (long long int i = 1;i <= n;i++)
	{
		mark1[i] = 0;
	}


	cur = 1;
	long long int cid = 1;

	vector <long long int> c = {0}, dp = {0};

	do
	{
		if (cid > lp)
		{
			ans[cur] += lp;
			mark1[cur] = 1;
			bfs.push(cur);
			c.push_back(cur);
			dp.push_back(0);
		}
		id[cur] = cid++;
		cur = nxt[cur];
	}while (cid <= l + lp);

	dp.push_back(0);

	while (bfs.size())
	{
		long long int v = bfs.front();
		bfs.pop();
		for (auto u : ne[v])
		{
			if (mark1[u])
			{
				continue;
			}
			mark1[u] = 1;
			dis[u] = dis[v] + 1;
			bfs.push(u);

			if (id[u] == 0)
			{
				id[u] = id[v];
				ans[sv] += n;
			}

			if (id[u] == 1)
			{
				continue;
			}

			dp[0] += (min(id[u] - 1, lp) - 1) / l;

			long long int st;

			if (id[u] > lp)
			{
				st = id[u] - lp + (k - lp - dis[u]) % l;
			}
			else
			{
				st = 1 + (k - (id[u] - 1) - dis[u]) % l;
			}

			st %= l;
			if (st == 0)
			{
				st = l;
			}
			long long int fn;
			long long int hmf;
			if (id[u] <= lp)
			{
				fn = st + id[u] - 1 - 1;
				hmf = id[u] - 1 - 1;
			}
			else
			{
				fn = st + lp - 1;
				hmf = lp - 1;
			}
			fn %= l;

			if (fn == 0)
			{
				fn = l;
			}

			dp[st]++;
			dp[fn + 1]--;
			if (fn + 1 <= st)
			{
				dp[0]++;
			}
		}
	}
	long long int pl = 0;
	for (long long int i = 0;i <= l;i++)
	{
		if (lp)
		pl += dp[i];
		ans[c[i]] += pl;
	}

	cur = csv;
	while (nxt[cur] != csv)
	{
		cur = nxt[cur];
	}

	for (auto it = ne[csv].begin();it != ne[csv].end();it++)
	{
		if ((*it) == cur)
		{
			ne[csv].erase(it);
			break;
		}
	}

	fr.init();
	nocl.init();
	sr.init();

	htl[cur] = 1;
	init(cur);
	fdfs(cur);
	ldfs(csv);

	for (long long int i = 1;i <= n;i++)
	{
		cout << ans[i] << '\n';
	}
}

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