求 hack
查看原帖
求 hack
377873
EricWan楼主2023/10/2 21:43
#include <bits/stdc++.h>
#define int long long
#define SON(a,b) for (auto a : son[b])
#define MAXN 100005
using namespace std;
int n, k, q_, r, x, y, z, vis[MAXN], s_[MAXN], s[MAXN], ex[MAXN], ey[MAXN], ez[MAXN], fa[MAXN], l[MAXN], f[MAXN][20], anc[MAXN][20], deepth[MAXN], len[MAXN][20], length, ans;
vector<pair<int,int> > v[MAXN], son[MAXN];
int deeper(int x, int y)
{
	if (deepth[x] >= deepth[y])
	{
		return x;
	}
	return y;
}
void dfsmaketree(int id, int de)
{
	vis[id] = 1;
	deepth[id] = de;
	for (auto j : v[id])
	{
		int i = j.first;
		if (!vis[i])
		{
			son[id].push_back({i,j.second});
			fa[i] = id;
			len[i][0] = j.second;
			dfsmaketree(i, de + 1);
		}
	}
}
void dfs_anc(int id)
{
	anc[id][0] = fa[id];
	for (int i = 1; anc[id][i - 1] != 0; i++)
	{
		anc[id][i] = anc[anc[id][i - 1]][i - 1];
		if (anc[id][i]) len[id][i] = len[id][i - 1] + len[anc[id][i - 1]][i - 1];
	}
	SON(i,id)
	{
		dfs_anc(i.first);
	}
}
void dfs_l(int id)
{
	SON(i,id)
	{
		dfs_l(i.first);
		s[id] |= s[i.first];
		l[id] = min(l[id],l[i.first] + len[i.first][0]);
	}
	if (s_[id]) l[id] = 0;
	f[id][0] = l[id];
}
void dfs_f(int id)
{
	f[id][0] = min(f[id][0],l[fa[id]] + len[id][0]);
	for (int i = 1; anc[id][i] != 0; i++)
	{
		f[id][i] = min(f[id][i - 1], f[anc[id][i - 1]][i - 1] + len[id][i - 1]);
	}
	SON(i,id)
	{
		dfs_f(i.first);
	}
}
int LCA(int x, int y)
{
	if (deeper(x,y) != x)
	{
		swap(x,y);
	}
	int k = 19;
	while (deepth[x] > deepth[y])
	{
		if (deepth[anc[x][k]] >= deepth[y])
		{
			x = anc[x][k];
		}
		k--;
	}
	if (x == y) return x;
	for (int i = 19; i >= 0; i--)
	{
		if (anc[x][i] != anc[y][i])
		{
			x = anc[x][i];
			y = anc[y][i];
		}
	}
	return fa[x];
}
signed main()
{
	memset(l,0x3f,sizeof(l));
	memset(f,0x3f,sizeof(f));
    cin >> n >> k >> q_ >> r;
    for (int i = 1; i < n; i++)
    {
        cin >> x >> y >> z;
        v[x].push_back({y,z});
        v[y].push_back({x,z});
        ex[i] = x;
        ey[i] = y;
        ez[i] = z;
    }
    for (int i = 1; i <= k; i++)
    {
        cin >> x;
        s_[x] = s[x] = 1;
    }
    dfsmaketree(r,1);//fa,deepth,son
    dfs_anc(r);//anc
    dfs_l(r);//l,s,f[i][0]
    dfs_f(r);//f
    while (q_--)
    {
        cin >> y >> z;
        x = deeper(ex[y],ey[y]);
        y = ex[y] + ey[y] - deeper(ex[y],ey[y]);
    	if (LCA(x,z) != x)
    	{
    		cout << "escaped\n";
    	}
    	else
    	{
    		if (s[x] == 0)
    		{
    			cout << "oo\n";
    		}
    		else
    		{
    			ans = l[z];
    			length = 0;
    			for (int i = 19; i >= 0; i--)
    			{
    				if (anc[z][i] != 0)
    				{
    					// cout << "renewans: " << z << " " << length << " " << f[z][i] + length << endl;
    					ans = min(ans,f[z][i] + length);
    					length += len[z][i];
    					z = anc[z][i];
    				}
    			}
    			cout << ans << endl;
    		}
    	}
    }
    // cout << "fa:\t";
    // for (int i = 1; i <= n; i++)
    // {
    	// cout << fa[i] << " ";
    // }
    // cout << endl;
    // cout << "s:\t";
    // for (int i = 1; i <= n; i++)
    // {
    	// cout << s[i] << " ";
    // }
    // cout << endl;
    // cout << "s_:\t";
    // for (int i = 1; i <= n; i++)
    // {
    	// cout << s_[i] << " ";
    // }
    // cout << endl;
    // cout << "s:\t";
    // for (int i = 1; i <= n; i++)
    // {
    	// cout << s[i] << " ";
    // }
    // cout << endl;
    // cout << "l:\t";
    // for (int i = 1; i <= n; i++)
    // {
		// cout << min(100ll, l[i]) << "\t";
    // }
    // cout << endl;
    // cout << "deepth:\t";
    // for (int i = 1; i <= n; i++)
    // {
    	// cout << deepth[i] << " ";
    // }
    // cout << endl;
    // cout << "len:\n";
    // for (int i = 1; i <= n; i++)
    // {
		// cout << " " << i << ": ";
		// for (int j = 0; j <= 5; j++)
		// {
			// cout << len[i][j] << " ";
		// }
		// cout << endl;
    // }
    // cout << "anc:\n";
    // for (int i = 1; i <= n; i++)
    // {
		// cout << " " << i << ": ";
		// for (int j = 0; j <= 5; j++)
		// {
			// cout << anc[i][j] << " ";
		// }
		// cout << endl;
    // }
    // cout << "f:\n";
    // for (int i = 1; i <= n; i++)
    // {
		// cout << " " << i << ": ";
		// for (int j = 0; j <= 5; j++)
		// {
			// cout << min(100ll, f[i][j]) << "\t";
		// }
		// cout << endl;
    // }
    // cout << "son:\n";
    // for (int i = 1; i <= n; i++)
    // {
		// cout << " " << i << ": ";
		// for (auto j : son[i])
		// {
			// cout << j.first << "," << j.second << " ";
		// }
		// cout << endl;
    // }
    // for (int i = 1; i <= n; i++)
    // {
		// for (int j = 1; j <= n; j++)
		// {
			// cout << LCA(i,j) << " ";
		// }
		// cout << endl;
    // }
    return 0;
}

只有 23 分。

2023/10/2 21:43
加载中...