P9026 [CCC 2021 S4] Daily Commute

题目描述

已知有 $N$ 个地铁站，你家在 $1$，学校在 $N$。

有 $W$ 条单向人行道。经过需要一分钟。

此外还有一条环形地铁线路，依次经过 $S_1,S_2,\cdots ,S_N$，且保证 $S_1=1$。每天有且仅有一辆地铁在 $0$ 时刻从 $S_1$ 出发，并且恰好在第 $i$ 分钟到达 $S_i$。

在接下来 $D$ 天中：

• 交换 $S_{X_i}$ 和 $S_{Y_i}$。注意修改是永久的。
• 查询从 $1$ 到 $N$ 的最短用时。你出发时地铁在 $1$。

输入格式

第一行：$N,W,D$。

接下来 $W$ 行：$A_i,B_i$ 表示单向人行道。

接下来一行 $N$ 个数：$S$。

接下来 $D$ 行：$X_i,Y_i$，保证 $2\le X_i,Y_i\le N,X_i\ne Y_i$。

输出格式

$D$ 行，每天的答案。

输入输出样例 #1

输入 #1

4 3 3
1 2
3 4
4 1
1 4 3 2
3 4
4 2
3 2

输出 #1

1
2
3

说明/提示

$$3\le N\le 200000,0\le W\le 200000,1\le D\le 200000$$

译自 CCC2021 S4。

请注意常数。

C++实现

#include<stdio.h>
#include<queue>
#define N 222222
#define pr pair<int,int> 
using namespace std;
inline char nc(){
	static char buf[99999],*l,*r;
	return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x){
	char c=nc();for(;c<'0'||'9'<c;c=nc());
	for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
inline void pc(const char&c){
	static char buf[99999],*r=buf;
	(!c||(*r++=c,r==buf+99999))&&(fwrite(buf,1,r-buf,stdout),r=buf);
}
inline void pi(const int&x){if(x>9)pi(x/10);pc(x%10+'0');}
int n,m,d,s[N],a[N],h[N],e[N],nxt[N],dis[N];
priority_queue<pr,vector<pr>,greater<pr> >qwq;deque<int>q;
main(){
	read(n);read(m);read(d);
	for(int i=1,u,v;i<=m;++i)read(u),read(v),--u,--v,
		e[i]=u,nxt[i]=h[v],h[v]=i;
	for(int i=0,x;i<n;read(s[i]),a[--s[i]]=i,dis[i++]=1<<30);
	q.emplace_back(n-1);dis[n-1]=0;
	for(int i;q.size();)	{
		i=q.front();q.pop_front();
		for(int j=h[i];j;j=nxt[j])if(dis[e[j]]>>30)
			dis[e[j]]=dis[i]+1,q.emplace_back(e[j]);
	}
	for(int i=0;i<n;++i)qwq.emplace(dis[i]+a[i],i);
	for(int u,v;d--;pi(qwq.top().first),pc('\n'))	{
		read(u);read(v);--u;--v;
		swap(s[u],s[v]);
		u=s[u];v=s[v];
		swap(a[u],a[v]);
		qwq.emplace(dis[u]+a[u],u);qwq.emplace(dis[v]+a[v],v);
		for(;qwq.top().first^dis[qwq.top().second]+a[qwq.top().second];
			qwq.pop());
	}
	pc(0);
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容