[JOISC2022]监狱
容易发现一个人一旦开始走就不会停。
因此如果一个人的开始点 \(s_i\) 在另一个人的 \(s_j\to t_j\) 上，那么 \(i\) 的出发时间一定小于 \(j\)，对于 \(t_i\) 在路径上同理。
因此可以建出一个图，那么合法当且仅当图是 \(DAG\) 。
建图可以用倍增优化建图，时空复杂度 \(O(n\log n)\) 。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
const int M = 2e7+7;
int n,m;
template <typename T>inline void read(T &x){
x=0;char c=getchar();bool f=0;
for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+(c^48);
x=(f?-x:x);
}
vector<int> G[N];
int dep[N];
struct edge
{
int y,next;
}e[M];
int link[M],deg[M],t=0;
int A[N][19],B[N][19],fa[N][19],tot=0;
void clr()
{
for(int i=1;i<=n;i++)G[i].clear();
for(int i=1;i<=n;i++)
for(int k=0;k<=18;k++)
A[i][k]=B[i][k]=fa[i][k]=0;
for(int i=1;i<=tot;i++)
link[i]=0,deg[i]=0;
t=0;tot=0;
}
void add(int x,int y)
{
e[++t].y=y;
deg[y]++;
e[t].next=link[x];
link[x]=t;
}
void mo(int &x){if(!x)x=++tot;}
void dfs(int x,int pre)
{
dep[x]=dep[pre]+1;
fa[x][0]=pre;
mo(A[x][0]);mo(B[x][0]);
for(int k=1;fa[x][k-1];k++)
{
int y=fa[x][k-1];
fa[x][k]=fa[y][k-1];
if(!A[y][k-1])continue;
mo(A[x][k]);add(A[x][k],A[x][k-1]);add(A[x][k],A[y][k-1]);
mo(B[x][k]);add(B[x][k-1],B[x][k]);add(B[y][k-1],B[x][k]);
}
for(int y:G[x])
{
if(y==pre)continue;
dfs(y,x);
}
}
int LCA(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
for(int k=18;k>=0;k--)
if(dep[fa[x][k]]>=dep[y])x=fa[x][k];
if(x==y)return x;
for(int k=18;k>=0;k--)
if(fa[x][k]!=fa[y][k])
{
x=fa[x][k];
y=fa[y][k];
}
return fa[x][0];
}
int nxto(int x,int y)
{
if(x!=LCA(x,y))return fa[x][0];
for(int k=18;k>=0;k--)
if(dep[fa[y][k]]>dep[x])y=fa[y][k];
return y;
}
void AddA(int x,int y,int o)
{
if(dep[x]<dep[y])swap(x,y);
for(int k=18;k>=0;k--)
if(dep[fa[x][k]]>=dep[y])
{
add(o,A[x][k]);
x=fa[x][k];
}
if(x==y)
{
add(o,A[x][0]);
return;
}
for(int k=18;k>=0;k--)
if(fa[x][k]!=fa[y][k])
{
add(o,A[x][k]);
add(o,A[y][k]);
x=fa[x][k];
y=fa[y][k];
}
add(o,A[x][1]);
add(o,A[y][0]);
}
void AddB(int x,int y,int o)
{
if(dep[x]<dep[y])swap(x,y);
for(int k=18;k>=0;k--)
if(dep[fa[x][k]]>=dep[y])
{
add(B[x][k],o);
x=fa[x][k];
}
if(x==y)
{
add(B[x][0],o);
return;
}
for(int k=18;k>=0;k--)
if(fa[x][k]!=fa[y][k])
{
add(B[x][k],o);
add(B[y][k],o);
x=fa[x][k];
y=fa[y][k];
}
add(B[x][1],o);
add(B[y][0],o);
}
queue<int> q;
void solve()
{
clr();
read(n);
for(int i=1;i<n;i++)
{
int x,y;
read(x);read(y);
G[x].push_back(y);
G[y].push_back(x);
}
tot=n;
dfs(1,0);
read(m);
while(m--)
{
int x,y;
read(x);read(y);
int o=++tot;
add(o,B[x][0]);add(A[y][0],o);
AddB(nxto(x,y),y,o);
AddA(nxto(y,x),x,o);
}
while(!q.empty())q.pop();
for(int i=1;i<=tot;i++)
if(!deg[i])q.push(i);
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=link[x];i;i=e[i].next)
{
int y=e[i].y;
deg[y]--;
if(!deg[y])q.push(y);
}
}
// printf("\n");
// for(int x=1;x<=tot;x++)
// if(deg[x])
// for(int i=link[x];i;i=e[i].next)
// {
// int y=e[i].y;
// if(deg[y])printf("%d %d\n",x,y);
// }
for(int i=1;i<=tot;i++)
if(deg[i])
{
printf("No\n");
return;
}
printf("Yes\n");
}
int main()
{
int T;
read(T);
while(T--)
{
solve();
}
return 0;
}
[JOISC2022]京都观光
比较厉害的题。
发现路径可以分成若干个点，相邻两点之间只会拐一次，称这些点为关键点。
那么我们考虑从 关键点\((i,x)\) 到 关键点\((j,y)\)的路径。
如果这两个点相邻，那么有两种走法：
\(C_1=a_i(y-x)+b_y(j-i)\) 和 \(C_2=a_j(y-x)+b_x(j-i)\) 。
如果不相邻，那不妨设经过了中间行 \(k\) (否则可以归纳)，那么代价为 \(C_3=a_k(y-x)+b_x(k-i)+b_y(j-k)\)。
容易发现，只有当 \(C3<C1\& C3<C2\) 时 \(k\) 是有用的。
这等价于 $$\frac{a_k-a_i}{k-i} < \frac{b_y-b_x}{y-x}<\frac{a_j-a_k}{j-k}$$ 。
把 \((i,a_i)\) 看成一个点，那么相邻关键点的斜率是递增的，也就是说，我们最终的 \(a,b\) 都是下凸壳 。
具体的，我们先对 \(a,b\) 分别求下凸壳，最终的走法就是这两个凸壳的闵可夫斯基和。
复杂度 \(O(n+m)\)
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
int stk[N],top=0;
int ConVexHull(int *a,int n,int *A)
{
top=0;
for(int i=1;i<=n;i++)
{
while(top>1&&1ll*(a[stk[top]]-a[stk[top-1]])*(i-stk[top])>=1ll*(a[i]-a[stk[top]])*(stk[top]-stk[top-1]))top--;
stk[++top]=i;
}
for(int i=1;i<=top;i++)A[i]=stk[i];
return top;
}
int A[N],B[N],a[N],b[N];
int n,m;
typedef long long LL;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=m;i++)scanf("%d",&b[i]);
n=ConVexHull(a,n,A);
m=ConVexHull(b,m,B);
int x=1,y=1;
LL ans=0;
for(int i=1;x<n||y<m;i++)
{
if(x==n)
{
ans+=1ll*a[A[x]]*(B[y+1]-B[y]);
y++;
continue;
}
if(y==m)
{
ans+=1ll*b[B[y]]*(A[x+1]-A[x]);
x++;
continue;
}
if(1ll*(a[A[x+1]]-a[A[x]])*(B[y+1]-B[y])<1ll*(b[B[y+1]]-b[B[y]])*(A[x+1]-A[x]))
{
ans+=1ll*b[B[y]]*(A[x+1]-A[x]);
x++;
continue;
}
ans+=1ll*a[A[x]]*(B[y+1]-B[y]);
y++;
continue;
}
cout<<ans;
return 0;
}