QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#60168#4809. Maximum RangexiaoyaowudiWA 12ms73400kbC++178.7kb2022-11-03 10:19:352022-11-03 10:19:38

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-03 10:19:38]
  • 评测
  • 测评结果：WA
  • 用时：12ms
  • 内存：73400kb
查看
  • [2022-11-03 10:19:35]
  • 提交

answer

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <functional>
constexpr int N(400010),inf(1.01e9);
using t3i=std::tuple<int,int,int,int>;
using veci=std::vector<int>;
int bcnt,n,m;
t3i mxm[N],mnm[N];
veci pts[N],ts[N<<1],gs[N];
// #define DEBUG {std::cout<<__FUNCTION__<<std::endl;}
#define DEBUG
std::vector<std::pair<int,int>> eds[N],es[N];
void tarjan(int u)
{
	static std::tuple<int,int,int> stk[N];
	static int top,dfn[N],low[N],dcnt;
	dfn[u]=low[u]=++dcnt;stk[++top]={u,-1,-1};
	for(auto [v,w]:es[u])
	{
		if(!dfn[v])
		{
			tarjan(v);low[u]=std::min(low[u],low[v]);
			if(low[v]==dfn[u])
			{
				int k=++bcnt;
				pts[k].emplace_back(u);
				mxm[k]={-inf,0,0,0},mnm[k]={inf,0,0,0};
				while(1)
				{
					auto [x,y,w]=stk[top--];
					// std::cerr<<x<<" "<<y<<" "<<w<<std::endl;
					if(~y) eds[k].emplace_back(x,y),mxm[k]=std::max(mxm[k],{w,x,y,k+n}),mnm[k]=std::min(mnm[k],{w,x,y,k+n});
					else
					{
						pts[k].emplace_back(x);
						if(x==v) break;
					}
				}
				if(eds[k].size()>1)
				{
					for(int v:pts[k]) ts[k+n].emplace_back(v),ts[v].emplace_back(k+n);
				}
			}
		}
		else if(dfn[v]<dfn[u]) stk[++top]={u,v,w},low[u]=std::min(low[u],dfn[v]);
	}
}
// std::pair<veci,veci> calc(const veci &vs,const veci &vall)
// {
// 	DEBUG;
// 	// if(m==98516)
// 	// {
// 	// 	for(int u:vs) if(std::find(vall.begin(),vall.end(),u)==vall.end())
// 	// 	{
// 	// 		std::cout<<"can't find "<<u<<std::endl;
// 	// 	}
// 	// }
// 	int l=vs.size(),u=vs[0],v=vs[l-1];
// 	static int idx[N],fv[N];
// 	// static bool mk[N];
// 	// for(int i:vall) fu[i]=fv[i]=0,mk[i]=false;
// 	for(int i:vall) fv[i]=0,idx[i]=-100;
// 	for(int i(0);i<l;++i) idx[vs[i]]=i;
// 	std::function<void(int,int,int*)> dfs=[&dfs](int u,int fa,int *ff){ff[u]=fa;if(mk[u]) return;for(int v:gs[u]) if(!ff[v]) dfs(v,u,ff);};
// 	for(int k:gs[u]) if(k==v)
// 	{
// 		return {vs,{u,v}};
// 	}
// 	fv[v]=-1;for(int k:gs[v]) if(!mk[k] && !fv[k]) dfs(k,v,fv);
// 	// if(m==98516) std::cout<<"❤"<<std::endl;
// 	if(fv[u])
// 	{
// 		// if(n==99996 && m==100000) std::cout<<"❤gyc"<<std::endl;
// 		veci res;
// 		for(int i(u);~i;i=fv[i]) res.emplace_back(i);
// 		// if(m==98516)
// 		// {
// 		// 	// std::cout<<"end"<<std::endl;
// 		// 	for(int i(0);i<std::min<int>(5,vs.size());++i) std::cout<<vs[vs.size()-i-1]<<" ";std::cout<<std::endl;
// 		// 	for(int i(0);i<std::min<int>(5,res.size());++i) std::cout<<res[res.size()-i-1]<<" ";std::cout<<std::endl;
// 		// }
// 		return {vs,res};
// 	}
// 	// if(m==98516) std::cout<<"❤"<<std::endl;
// 	int p1(l-2);while(!fv[vs[p1]]) ++p1;
// 	// if(m==98516) std::cout<<p1<<" "<<l<<std::endl;
// 	// if(m==98516) std::cout<<"❤"<<std::endl;
// 	int p2(p1+1);while(!fu[vs[p2]]) ++p2;
// 	// if(m==98516) std::cout<<"❤"<<std::endl;
// 	// if(m==98516) std::cout<<p1<<" "<<p2<<" "<<l<<std::endl;
// 	veci r1;for(int i(vs[p2]);~i;i=fu[i]) r1.emplace_back(i);std::reverse(r1.begin(),r1.end());r1.insert(r1.end(),vs.begin()+p2+1,vs.end());
// 	veci r2;r2.insert(r2.begin(),vs.begin(),vs.begin()+p1);for(int i(vs[p1]);~i;i=fv[i]) r2.emplace_back(i);
// 	// if(m==98516) for(int i(0);i<std::min<int>(5,r1.size());++i) std::cout<<r1[i]<<" ";std::cout<<std::endl;
// 	// if(m==98516) for(int i(0);i<std::min<int>(5,r2.size());++i) std::cout<<r2[i]<<" ";std::cout<<std::endl;
// 	return {r1,r2};
// }
std::pair<veci,veci> calc(const veci &vs,const veci &vall)
{
	DEBUG;
	int l(vs.size()),u(vs[0]),v(vs[l-1]),k(vs[1]);
	static int idx[N];
	for(int i:vall) idx[i]=-1;
	for(int i(0);i<l;++i) idx[vs[i]]=i;
	veci r1({u}),r2({u,k});int p1(u),p2(k);
	static int fa1[N],fa2[N];
	static bool vis1[N],vis2[N];
	for(int i:vall) vis1[i]=vis2[i]=false,fa1[i]=fa2[i]=0;
	int *f1(fa1),*f2(fa2);bool *v1(vis1),*v2(vis2);
	// std::cout<<u<<" "<<v<<" "<<k<<std::endl;
	// for(int i:vs) std::cout<<i<<" ";std::cout<<std::endl;
	while(1)
	{
		std::cout<<p1<<" "<<p2<<std::endl;
		if(idx[p1]>idx[p2]) std::swap(p1,p2),std::swap(f1,f2),std::swap(v1,v2),r1.swap(r2);
		if(p2==v)
		{
			for(int i(idx[p1]+1);i<l;++i) r1.emplace_back(vs[i]);
			break;
		}
		int mxi(-1);
		std::function<void(int,int)> dfs=[&](int u,int fa)->void{v1[u]=true;f1[u]=fa;mxi=std::max(mxi,idx[u]);if(idx[u]>=idx[p2]) return;
			for(int t:gs[u]) if(!v1[t]) dfs(t,u);};
		dfs(p1,0);
		int len(r1.size());
		for(int t(vs[mxi]);t!=p1;t=f1[t]) r1.emplace_back(t);
		std::reverse(r1.begin()+len,r1.end());
		p1=vs[mxi];
	}
	return {r1,r2};
}
veci solve_path(veci pts,int u,int v,int frb,int pre)
{
	DEBUG;
	static int fs[N];
	static bool vis[N];
	fs[pre]=0;
	std::function<void(int,int)> dfs=[&](int u,int fa)->void{fs[u]=fa;vis[u]=true;for(int v:gs[u]) if(!vis[v] && v!=frb) dfs(v,u);};
	dfs(v,pre);
	veci ret;
	for(int k:pts) vis[k]=false;
	for(int i(u);i;i=fs[i]) ret.emplace_back(i);
	// if(n==99996 && m==100000){std::cout<<*ret.rbegin()<<" "<<v<<" "<<pre<<std::endl;}
	return ret;
}
std::pair<veci,veci> solve1(int idx,int u,int v,int s)
{
	DEBUG;
	idx-=n;
	for(auto [u,v]:eds[idx]) gs[u].emplace_back(v),gs[v].emplace_back(u);
	std::pair<veci,veci> res;
	if(u==s)
	{
		res=calc({s,v},pts[idx]);
	}
	else
	{
		res=calc(solve_path(pts[idx],s,v,u,u),pts[idx]);
	}
	for(int u:pts[idx]) gs[u].clear();
	return res;
}
std::pair<veci,veci> solve2(int idx,int u,int v)
{
	DEBUG;
	// if(m==98516) std::cout<<u<<" "<<v<<std::endl;
	idx-=n;
	for(auto [u,v]:eds[idx]) gs[u].emplace_back(v),gs[v].emplace_back(u);
	auto res=calc(solve_path(pts[idx],u,v,0,0),pts[idx]);
	for(int u:pts[idx]) gs[u].clear();
	return res;
}
veci solve3(int idx,int u,int v,int s,int t)
{
	DEBUG;
	idx-=n;
	for(auto [u,v]:eds[idx]) gs[u].emplace_back(v),gs[v].emplace_back(u)/*,std::cout<<"e "<<u<<" "<<v<<std::endl*/;
	auto hp=[](std::pair<veci,veci> pr,veci vall)->veci
	{
		auto [p1,p2]=pr;
		std::reverse(p2.begin(),p2.end());
		p1.pop_back();p2.pop_back();
		p1.insert(p1.end(),p2.begin(),p2.end());
		for(int v:vall) gs[v].clear();
		return p1;
	};
	if(v==s || v==t) return hp(calc({u,v,(s^t^v)},pts[idx]),pts[idx]);
	else if(u==s || u==t) return hp(calc({v,u,(s^t^u)},pts[idx]),pts[idx]);
	auto pt=solve_path(pts[idx],v,s,t,t);
	int hu=-1,len=pt.size();
	for(int k(0);k<len;++k) if(pt[k]==u){hu=k;break;}
	// if(n==99997) std::cout<<hu<<std::endl;
	if(~hu)
	{
		pt.erase(pt.begin()+1,pt.begin()+hu);
	}
	else pt.insert(pt.begin(),u);
	// for(int i=0;i<std::min<int>(pt.size(),10);++i) std::cout<<pt[i]<<" ";std::cout<<std::endl;
	return hp(calc(pt,pts[idx]),pts[idx]);
}
int main()
{
	DEBUG;
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);std::cin>>n>>m;
	for(int i(1),u,v,w;i<=m;++i) std::cin>>u>>v>>w,es[u].emplace_back(v,w),es[v].emplace_back(u,w);
	tarjan(1);
	// if(m==98516) std::cout<<"❤"<<std::endl;
	static bool vis[N<<1];
	std::function<void(int,t3i&,t3i&)> dfs1=[&dfs1](int u,t3i &mx,t3i &mn)->void
	{
		if(u>n) mx=std::max(mxm[u-n],mx),mn=std::min(mnm[u-n],mn);vis[u]=true;
		for(int v:ts[u]) if(!vis[v]) dfs1(v,mx,mn);
	};
	int ans=-1,su,sv,sk,tu,tv,tk;
	for(int i(1);i<=n;++i) if(!vis[i] && ts[i].size())
	{
		t3i mn{inf,0,0,0},mx{-inf,0,0,0};
		dfs1(i,mx,mn);
		auto [w1,e1u,e1v,v1]=mn;auto [w2,e2u,e2v,v2]=mx;
		if(w2-w1>ans)
		{
			ans=w2-w1;
			su=e1u;sv=e1v;sk=v1;
			tu=e2u;tv=e2v;tk=v2;
		}
	}
	std::cout<<ans<<std::endl;
	if(sk!=tk)
	{
		static int ff[N<<1];
		std::function<void(int,int)> dfs2=[&dfs2](int u,int fa)->void{ff[u]=fa;for(int v:ts[u])if(fa!=v) dfs2(v,u);};
		dfs2(tk,0);
		static int vs[N<<1],vc;
		for(int i(sk);i;i=ff[i]) vs[++vc]=i;
		auto [r1,r2]=solve1(sk,su,sv,vs[2]);
		std::reverse(r1.begin(),r1.end());std::reverse(r2.begin(),r2.end());
		for(int i=3;i<vc;i+=2)
		{
			auto [c1,c2]=solve2(vs[i],vs[i-1],vs[i+1]);
			c1.erase(c1.begin());c2.erase(c2.begin());
			r1.insert(r1.end(),c1.begin(),c1.end());
			r2.insert(r2.end(),c2.begin(),c2.end());
		}
		auto [c1,c2]=solve1(tk,tu,tv,vs[vc-1]);
		// std::reverse(c1.begin(),c1.end());std::reverse(c2.begin(),c2.end());
		c1.erase(c1.begin());c2.erase(c2.begin());
		DEBUG;
		r1.insert(r1.end(),c1.begin(),c1.end());
		r2.insert(r2.end(),c2.begin(),c2.end());
		std::reverse(r2.begin(),r2.end());r1.erase(--r1.end());r2.erase(--r2.end());
		// if(n==99996 && m==100000){
		// 	for(int i(0);i<std::min<int>(5,r1.size());++i) std::cout<<r1[i]<<" ";std::cout<<std::endl;
		// 	for(int i(0);i<std::min<int>(5,r2.size());++i) std::cout<<r2[i]<<" ";std::cout<<std::endl;
		// }
		r1.insert(r1.end(),r2.begin(),r2.end());
		std::cout<<r1.size()<<std::endl;
		for(int v: r1) std::cout<<v<<" ";std::cout<<std::endl;
	}
	else
	{
		auto r1=solve3(sk,su,sv,tu,tv);
		std::cout<<r1.size()<<std::endl;
		for(int v:r1) std::cout<<v<<" ";std::cout<<std::endl;
	}
	return 0;
}
源文件, 语言: C++17

詳細信息

Test #1:

score: 0
Wrong Answer
time: 12ms
memory: 73400kb

input:

5 7
1 2 1
1 3 -2
2 3 1
3 4 3
4 5 1
1 5 -1
2 5 2

output:

5
1 3
4 3
4
1 3 4 5

result:

wrong answer Cycle does not contain any edges
English 繁體中文 简体中文

伺服器時間: 2024-12-02 18:36:46 | 開源專案