多校省选模拟4

T1 图论题

从 s 和 t 分别跑个最短路，然后建出到 s 的凸包，用 t 二分去就行了

从 s 跑 k 次同时维护李超树可以求出连 k 条边的最优解

T2 构造题

没想懂细节

T3 数据结构题

因为是顺序改题，就没有然后了，，，

代码

T1

#include
using namespace std;
#define il inline
#define int long long
const int N=200011;
const int inf=1e18;
struct bag_{int x,y;friend bool operator<(bag_ a,bag_ b){return a.x!=b.x?a.xb.y;}}now;
struct e_{int v,w;friend bool operator<(e_ a,e_ b){return a.w>b.w;}};
bool jud[N];
int n,m,s,t;
int d[2][N];
vector v[2][N];
vector bag;
priority_queue dui;
il int min_(int x,int y){return x>y?y:x;}
il double get_xl(bag_ a,bag_ b){return (b.y-a.y)/(b.x-a.x);}
il bool jd(bag_ a,bag_ b,bag_ c){return (b.x==c.x)||get_xl(a,c)>=get_xl(b,c);}
il int get_ans(bag_ a,int x){return x*x+a.y-2*a.x*x;}
il int read()
{
	int s=0;
	char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return s;
}
void dij(int x,bool jd)
{
	memset(d[jd],0x3f,sizeof(d[jd]));
	memset(jud,0,sizeof(jud));
	d[jd][x]=0;
	dui.push({x,0});
	e_ u;
	while(dui.size())
	{
		u=dui.top(),dui.pop();
		if(jud[u.v]) continue;
		jud[u.v]=1;
		for(e_ y : v[jd][u.v])
			if(d[jd][y.v]>d[jd][u.v]+y.w)
			{
				d[jd][y.v]=d[jd][u.v]+y.w;
				dui.push({y.v,d[jd][y.v]});
			}
	}
	return;
}
int two(int x)
{
	int sz=bag.size();
	if(sz==0) return inf;
	if(sz==1) return get_ans(bag[0],x);
	if(sz==2) return min_(get_ans(bag[0],x),get_ans(bag[1],x));
	if(get_ans(bag[0],x)>1;
		ansl=get_ans(bag[mid],x);
		ansr=get_ans(bag[mid+1],x);
		if(ansl1&&jd(bag[sz-2],bag[sz-1],now)) --sz,bag.pop_back();
		bag.push_back(now),++sz;
	}
	int ans=inf;
	for(int i=1;i<=n;++i) ans=min_(ans,d[0][i]+two(i));
	cout<