WA39pts求调
查看原帖
WA39pts求调
928568
zhouzihan20110620楼主2025/8/1 16:10
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
long long n, t, v, fth[500005], d[500005], dep[500005], rt[500005], st[500005][20], id[500005], sz[500005], a, b;
vector <int> g[500005], ag[500005];
queue <int> q;
bool vis[500005];
map <int, int> mp;
int fnd(int nowi)
{
	if (nowi == fth[nowi])
	{
		return nowi;
	}
	return fth[nowi] = fnd(fth[nowi]);
}
void unn(int x, int y)
{
	fth[fnd(x)] = fnd(y);
}
void dfs1(int nowi)
{
	for (int i = 1;i <= __lg(dep[nowi]);i++)
	{
		st[nowi][i] = st[st[nowi][i - 1]][i - 1];
	}
	for (int i = 0;i < ag[nowi].size();i++)
	{
		int v = ag[nowi][i];
		if (!vis[v])
		{
			continue;
		}
		rt[v] = rt[nowi];
		dep[v] = dep[nowi] + 1;
		st[v][0] = nowi;
		dfs1(v);
	}
}
void dfs2(int nowi)
{
	rt[nowi] = nowi;
	dep[nowi] = 1;
	bool flag = 1;
	for (int i = 0;i < g[nowi].size();i++)
	{
		int v = g[nowi][i];
		if (vis[v])
		{
			continue;
		}
		if (!sz[v])
		{
			sz[v] = sz[nowi] + 1;
			id[v] = id[nowi] + 1;
			dfs2(v);
			flag = 0;
		}
		else if (sz[v] < sz[nowi])
		{
			sz[v] = sz[nowi];
			dfs2(v);
			flag = 0;
		}
	}
	if (flag)
	{
		vis[nowi] = 1;
	}
}
int lca(int a, int b)
{
	if (dep[a] < dep[b])
	{
		swap(a, b);
	}
	for (int i = __lg(dep[a]);i >= 0;i--)
	{
		if (dep[st[a][i]] < dep[b])
		{
			continue;
		}
		a = st[a][i];
	}
	if (a == b)
	{
		return a;
	}
	for (int i = __lg(dep[a]);i >= 0;i--)
	{
		if (st[a][i] == st[b][i])
		{
			continue;
		}
		a = st[a][i];
		b = st[b][i];
	}
	return st[a][0];
}
int main()
{
	cin.tie(0)->ios::sync_with_stdio(false);
	cout.tie(0);
	cin >> n >> t;
	for (int i = 1;i <= n;i++)
	{
		fth[i] = i;
	}
	for (int i = 1;i <= n;i++)
	{
		cin >> v;
		g[i].emplace_back(v);
		ag[v].emplace_back(i);
		unn(i, v);
	}
	for (int i = 1;i <= n;i++)
	{
		if (!(d[i] = ag[i].size()))
		{
			vis[i] = 1;
			q.push(i);
		}
	}
	while (q.size())
	{
		int u = q.front();
		q.pop();
		for (int i = 0;i < g[u].size();i++)
		{
			int v = g[u][i];
			if (!--d[v])
			{
				vis[v] = 1;
				q.push(v);
			}
		}
	}
	for (int i = 1;i <= n;i++)
	{
		if (!vis[i])
		{
			rt[i] = i;
			dep[i] = 1;
			dfs1(i);
			if (!sz[i])
			{
				sz[i] = 1;
				dfs2(i);
			}
		}
	}
	while (t--)
	{
		cin >> a >> b;
		if (fnd(a) != fnd(b))
		{
			cout << "-1 -1\n";
		}
		else if (rt[a] == rt[b])
		{
			int lcaab = lca(a, b);
			cout << dep[a] - dep[lcaab] << " " << dep[b] - dep[lcaab] << "\n";
		}
		else
		{
			int ansa1 = dep[a] - 1 + (id[rt[b]] - id[rt[a]] + sz[rt[a]]) % sz[rt[a]], ansb1 = dep[b] - 1, ansa2 = dep[a] - 1, ansb2 = dep[b] - 1 + (id[rt[a]] - id[rt[b]] + sz[rt[a]]) % sz[rt[a]];
			if (max(ansa1, ansb1) < max(ansa2, ansb2))
			{
				cout << ansa1 << " " << ansb1 << "\n";
			}
			else if (max(ansa1, ansb1) > max(ansa2, ansb2))
			{
				cout << ansa2 << " " << ansb2 << "\n";
			}
			else
			{
				if (min(ansa1, ansb1) < min(ansa2, ansb2))
				{
					cout << ansa1 << " " << ansb1 << "\n";
				}
				else if (min(ansa1, ansb1) > min(ansa2, ansb2))
				{
					cout << ansa2 << " " << ansb2 << "\n";
				}
				else
				{
					if (ansa1 >= ansb1)
					{
						cout << ansa1 << " " << ansb1 << "\n";
					}
					else
					{
						cout << ansa2 << " " << ansb2 << "\n";
					}
				}
			}
		}
	}
	cout << endl;
	return 0;
}

rt

2025/8/1 16:10
加载中...