AtCoder AGC007E Shik and Travel (二分、DP、启发式合并)

题目链接

https://atcoder.jp/contests/agc007/tasks/agc007_e

题解

首先有个很朴素的想法是，二分答案\(mid\)后使用可行性DP, 设\(dp[u][x][y]\)表示\(u\)子树内是否可以找到一条路径，在经过第一个叶子前路程是\(x\), 经过最后一个叶子前路程是\(y\).

这个DP显然做了很多无用功，比如我们发现完全可以只记录true的状态\((x,y)\)，进一步发现如果合法状态\((x,y)\)存在另一合法状态\((x',y')\)满足\(x'\le x,y'<\le y\), 那么就没有必要存储\((x,y)\)了。于是我们按\(x\)递增的顺序存储\((x,y)\)，那么\(y\)一定是递减的。

这样简化之后，我们发现一个神奇的性质: 设\(S_u\)为\(u\)记录的集合，\(i\)和\(j\)为儿子，那么\(|S_u|\le 2\min(|S_i|,|S_j|)\). 这是因为\(x\)和\(y\)的取值都各有\(\min(|S_i|,|S_j|)\)种。

考虑合并的过程: 假设路径的开头在\(i\)内，那么我们需要找到\((x_1,y_1)\in S_i, (x_2,y_2)\in S_j\), 若\(y_1+v_i+v_j+x_2\le mid\), 则把\((x_1+v_i,y_2+w_j)\)加入\(S_u\). 这个显然可以用双指针优化. 路径的开头在\(j\)内也同理。

类似启发式合并可分析复杂度。算上二分总复杂度\(O(n\log^2n)\).

代码

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<cassert>

#include<vector>

#define llong long long

#define pll pair<llong,llong>

#define mkpr make_pair

using namespace std;

const int N = 1<<17;

int son[N+3][2];

llong w[N+3];

vector<pll> dp[N+3];

vector<pll> aux1,aux2;

int n,en;

llong mid;

void dfs(int u)

{

//	printf("dfs %d\n",u);

	dp[u].clear(); int ls = son[u][0],rs = son[u][1];

	if(!ls)

	{

		dp[u].push_back(mkpr(0ll,0ll));

		return;

	}

	dfs(ls); dfs(rs);

	aux1.clear(); aux2.clear();

	if(dp[rs].size())

	{

		int j = 0;

		for(int i=0; i<dp[ls].size(); i++)

		{

			while(j<dp[rs].size()-1 && dp[rs][j+1].first+dp[ls][i].second+w[ls]+w[rs]<=mid) {j++;}

			if(j<dp[rs].size() && dp[rs][j].first+dp[ls][i].second+w[ls]+w[rs]<=mid) {aux1.push_back(mkpr(dp[ls][i].first+w[ls],dp[rs][j].second+w[rs]));}

		}

	}

	if(dp[ls].size())

	{

		int j = 0;

		for(int i=0; i<dp[rs].size(); i++)

		{

			while(j<dp[ls].size()-1 && dp[ls][j+1].first+dp[rs][i].second+w[ls]+w[rs]<=mid) {j++;}

			if(j<dp[ls].size() && dp[ls][j].first+dp[rs][i].second+w[ls]+w[rs]<=mid) {aux2.push_back(mkpr(dp[rs][i].first+w[rs],dp[ls][j].second+w[ls]));}

		}

	}

	int j = 0,k = 0; llong cur = 1ll<<34;

	while(j<aux1.size() || k<aux2.size())

	{

		if(k==aux2.size() || (j<aux1.size() && aux1[j].first<=aux2[k].first))

		{

			if(aux1[j].second<cur) {dp[u].push_back(aux1[j]); cur = aux1[j].second;}

			j++;

		}

		else

		{

			if(aux2[k].second<cur) {dp[u].push_back(aux2[k]); cur = aux2[k].second;}

			k++;

		}

	}

}

bool check()

{

	dfs(1);

	if(dp[1].size()) {return true;}

	else {return false;}

}

int main()

{

	scanf("%d",&n);

	for(int i=2; i<=n; i++)

	{

		int u; llong x; scanf("%d%lld",&u,&x);

		w[i] = x; if(son[u][0]) son[u][1] = i; else son[u][0] = i;

	}

	llong left = 0ll,right = 1ll<<34;

	while(left<right)

	{

		mid = left+((right-left)>>1)

//		printf("mid=%lld\n",mid);

		bool ok = check();

		if(ok) {right = mid;}

		else {left = mid+1;}

	}

	printf("%lld\n",right);

	return 0;

}

巴特西

AtCoder AGC007E Shik and Travel (二分、DP、启发式合并)

题目链接

题解

代码

最新文章

热门文章