[luogu3573 POI2014] RAJ-Rally (拓扑排序 权值线段树)

传送门

Solution

在DAG中我们可以\(O(n)\)预处理\(Ds(u)\)表示从u表示以s为起点的最长路\(Dt(u)\)表示以u为终点的最长路，那么经过\((u,v)\)的最长路即为\(Dt(u)+Ds(t)+1\)

然后我们考虑如何快速枚举删哪个点来统计答案

emmm。。。懒得画图了，后面的去看这篇博客吧

Code

//By Menteur_Hxy

#include <cmath>

#include <vector>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define Re register

#define ls nd[cur][0]

#define rs nd[cur][1]

#define Ms(a,b) memset(a,(b),sizeof(a))

#define Ee(i,u) for(Re int i=head[u];i;i=nxt[i])

#define Fo(i,a,b) for(Re int i=(a),_=(b);i<=_;i++)

#define Ro(i,a,b) for(Re int i=(b),_=(a);i>=_;i--)

using namespace std;

inline int read() {

	int x=0,f=1;char c=getchar();

	while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}

	while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();

	return x*f;

}

const int N=10e5+10,M=2e6+10,INF=0x3f3f3f3f;

int n,m,cnt,ans=INF,aid;

int ind[N],nxt[M],to[M],head[N],que[N],ds[N],dt[N];

vector<int> V[N];

void add(int u,int v) {nxt[++cnt]=head[u],to[cnt]=v,head[u]=cnt;}

void Tsort() {

	int h=1,t=0;

	Fo(i,1,n) if(!ind[i]) que[++t]=i;

	while(h<=t) {

		int u=que[h++],v;

		Ee(i,u) if(!(--ind[v=(to[i])])) que[++t]=v;

	}

}

void pre_work() {

	Tsort();

	Ro(i,1,n) {

		int u=que[i],siz=V[u].size(),v;

		Fo(j,0,siz-1) v=V[u][j],ds[v]=max(ds[v],ds[u]+1);

	}

	Fo(i,1,n) {

		int u=que[i],v;

		Ee(j,u) v=to[j],dt[v]=max(dt[v],dt[u]+1);

	}

}

struct SMT{

	int nd[N<<2][2],sum[N<<2],tot,root;

	void clear() {Ms(nd,0);Ms(sum,0);tot=root=0;}

	void upd(int l,int r,int &cur,int k,int d) {

		if(!cur) cur=++tot;

		if(l==r) {sum[cur]+=d;return ;}

		int mid=(l+r)>>1;

		if(k<=mid) upd(l,mid,ls,k,d);

		else upd(mid+1,r,rs,k,d);

		sum[cur]=sum[ls]+sum[rs];

	}

	int qry(int l,int r,int cur) {

		if(l==r) return l;

		int mid=(l+r)>>1;

		if(sum[rs])	return qry(mid+1,r,rs);

		else return qry(l,mid,ls);

	}

}T;

void solve() {

	T.clear();

	Fo(i,1,n) T.upd(0,n,T.root,ds[i],1);

	Fo(i,1,n) {

		int u=que[i],siz=V[u].size();

		T.upd(0,n,T.root,ds[u],-1);

		Fo(j,0,siz-1) T.upd(0,n,T.root,dt[V[u][j]]+ds[u]+1,-1);

		int tmp=T.qry(0,n,T.root); if(tmp<ans) ans=tmp,aid=u;

		T.upd(0,n,T.root,dt[u],1);

		Ee(j,u) T.upd(0,n,T.root,dt[u]+ds[to[j]]+1,1);

	}

	printf("%d %d",aid,ans);

}

int main() {

	n=read();m=read();

	Fo(i,1,m) {

		int u=read(),v=read();

		add(u,v); ind[v]++;

		V[v].push_back(u);

	}

	pre_work(); solve();

	return 0;

}