题解：P11352 [NOISG 2024 Finals] Coin

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fir first
#define sec second
#define mk make_pair
using namespace std;
inline int read(){
	int x=0;bool f=0;char ch=getchar();
	while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int Maxn=8e5+5,inf=1e9+7;
int n,m;
struct edge{
	int u,v;
}e[Maxn];
int du[Maxn],f[Maxn];
int ans[Maxn];
vector<pii>G1[Maxn];
vector<int>G[Maxn];
multiset<int>s;
int tpu[Maxn];
inline void sol1(){
	memset(f,0x3f3f,sizeof f);
	s.clear();
	for(int i=1;i<=m;i++){
		du[e[i].v]++;
		G[e[i].u].emplace_back(e[i].v);
		G1[e[i].v].emplace_back(mk(e[i].u,i));
	}
	queue<int>h;
	for(int i=1;i<=n;i++)if(!du[i])h.push(i);
	int cnt=0;
	while(!h.empty()){
		int u=h.front();h.pop();
		tpu[++cnt]=u;
		for(pii it:G1[u]){
			int y=it.fir;
			s.erase(s.find(f[y]));f[y]=min(f[y],it.sec);s.insert(f[y]);
		}if(!s.empty())ans[u]=(*s.rbegin());
		for(int y:G[u]){
			if(!(--du[y]))h.push(y);
		}s.insert(f[u]);
	}
}

inline void sol2(){
	memset(f,0x3f3f,sizeof f);
	for(int i=1;i<=n;i++)G1[i].clear();
	for(int i=1;i<=m;i++)G1[e[i].u].emplace_back(mk(e[i].v,i));
	s.clear();
	for(int i=n;i;i--){
		int u=tpu[i];
		for(pii it:G1[u]){
			int y=it.fir;
			s.erase(s.find(f[y]));f[y]=min(f[y],it.sec);s.insert(f[y]);
		}if(!s.empty())ans[u]=max(ans[u],(*s.rbegin()));
		s.insert(f[u]);
	}
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=m;i++)e[i]={read(),read()};
	
	sol1();
	sol2();
	
	for(int i=1;i<=n;i++)printf("%d ",(ans[i]>m?-1:ans[i]));
	return 0;
}
/*
7 20
1 6
6 3
1 4
1 5
1 7
1 2
1 5
2 3
4 5
7 2
2 4
5 3
6 3
1 3
4 3
7 5
2 6
4 6
7 2
7 5

4 4
2 4
3 1
4 1
2 3
*/