第九个点一直MLE,求助
查看原帖
第九个点一直MLE,求助
227824
JK_LOVER楼主2020/7/21 19:16
#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return f?-x:x;
}
const int N = 501000;
int n,k,m1,m2;
struct dsu_edge{int x,y,w;}dsu_e[N<<1];
int dsu_fa[N],mst_e[N],mst_top;
bool dsu_cmp(dsu_edge a,dsu_edge b)
{
	return a.w < b.w;
}
int dsu_find(int x)
{
	return x==dsu_fa[x]?x:dsu_fa[x]=dsu_find(dsu_fa[x]);
}
void solve_dsu()
{
	for(int i = 1;i <= m1+m2;i++)
	{
		int a = dsu_e[i].x,b = dsu_e[i].y;
		a = dsu_find(a);
		b = dsu_find(b);
		if(a == b) continue;
		mst_e[i] = 1;
		dsu_fa[a] = b;
	}
}
struct segment_tree{
	int down,up;
}t[N<<2];
vector<int> G[N<<1],W[N<<1];
int top[N],son[N],si[N],d[N],id[N],f[N],map_e[N],seg_val[N],val_node[N],cnt_id = 0;
void build(int x,int l,int r)
{
//	cout<<"l:: "<<l<<" "<<" r:: "<<r<<endl;
	if(l==r) {
		if(l==1) return;
//		cout<<"segval   "<<seg_val[l]<<endl;
		t[x].up = (seg_val[l] == 0);
		t[x].down = 0;
		return;
	}
	int mid = l+r>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	t[x].up = t[x<<1|1].up + t[x<<1].up;
//	cout<<"t[x].up:: "<<t[x].up<<endl;
}
void dfs_dep(int x,int fa,int dep)
{
	d[x] = dep;f[x] = fa;si[x] = 1;
	//cout<<"x:: "<<x<<" fa:: "<<fa<<endl;
	for(int i = 0;i < G[x].size();i++)
	{
		int y = G[x].at(i);
		if(y == fa) continue;
		val_node[y] = W[x].at(i);
		dfs_dep(y,x,dep+1);
		si[x] += si[y];
		if(si[y] > si[son[x]])
		{
			son[x] = y;
		}
	}
}
void dfs_top(int x,int fa,int Top)
{
	//cout<<"x:: "<<x<<"  Top:: "<<Top<<endl;
	id[x] = ++cnt_id;seg_val[cnt_id] = val_node[x];top[x] = Top;
	if(son[x]) dfs_top(son[x],x,Top);
	for(int i = 0;i < G[x].size();i++)
	{
		int y = G[x].at(i);
		if(y == son[x] || y == fa) continue;
		dfs_top(y,x,y);
	}
}
void solve_mst()
{
	for(int i = 1;i <= m1+m2;i++)
	{
		if(mst_e[i])
		{
			//cout<<"mst_e[i]:: "<<i<<endl;
			dsu_edge a = dsu_e[i];
			G[a.x].push_back(a.y);
			G[a.y].push_back(a.x);
			W[a.x].push_back(a.w);
			W[a.y].push_back(a.w);
		}
	}
	dfs_dep(1,0,1);
	dfs_top(1,0,1);
	build(1,1,n);
}
void update(int x)
{
	if(t[x].down)
	{
		t[x<<1|1].down = t[x<<1].down = 1;
		t[x<<1|1].up = t[x<<1].up = 0;
		t[x].down = 0;
	}
	return;
}
void change(int x,int L,int R,int l,int r)
{
	if(r < L || l > R) return;
	if(L <= l && r <= R) {
		t[x].up = 0;
		t[x].down = 1;
		return;
	}
	update(x);
	int mid = l+r>>1;
	change(x<<1,L,R,l,mid);
	change(x<<1|1,L,R,mid+1,r); 
	t[x].up = t[x<<1].up + t[x<<1|1].up;
}
int ask(int x,int L,int R,int l,int r)
{
	if(r < L || l > R) return 0;
	if(L <= l && r <= R) return t[x].up;
	update(x);
	int mid = l+r>>1;
	return ask(x<<1,L,R,l,mid)+ask(x<<1|1,L,R,mid+1,r); 	
}
int work_edge(dsu_edge a)
{
	int x = a.x,y = a.y;
	int res = 0;
	while(top[x] != top[y])
	{
//		cout<<"X:: "<<x<<"  "<<"Y::" <<y<<endl;
		if(d[top[x]] < d[top[y]]) swap(x,y);
		res += ask(1,id[top[x]],id[x],1,n);
		change(1,id[top[x]],id[x],1,n);
		x = f[top[x]];
	}
	if(d[x] > d[y]) swap(x,y);
	res += ask(1,id[x]+1,id[y],1,n);
	change(1,id[x]+1,id[y],1,n);
//	cout<<"res:: "<<res<<endl;
	return res;
}
void solve_ans()
{
	long long ans = 0;
	for(int i = m1+1;i <= m1+m2;i++)
	{
		if(mst_e[i]) continue;
		ans += 1LL*dsu_e[i].w * work_edge(dsu_e[i]);
	}
//	cout<<"ask "<<ask(1,1,n,2,n)<<endl;
	if(ask(1,1,n,2,n) > 0) printf("-1\n");
	else printf("%lld\n",ans);
}
signed main()
{
	n = read();m1 = read();m2 = read();
	for(int i = 1;i <= n;i++) dsu_fa[i] = i;
	for(int i = 1;i <= m1;i++) 
	{
		dsu_e[i].x = read();
		dsu_e[i].y = read();
		dsu_e[i].w = 0;
	}
	for(int i = m1+1;i <= m1+m2;i++)
	{
		dsu_e[i].x = read();
		dsu_e[i].y = read();
		dsu_e[i].w = read();
	}
	sort(dsu_e+1,dsu_e+m1+m2+1,dsu_cmp);
	solve_dsu();
	solve_mst();
	solve_ans();
	return 0;
}
2020/7/21 19:16
加载中...