WA on #13 马蜂良好 悬关求条orz orz
查看原帖
WA on #13 马蜂良好 悬关求条orz orz
1121439
TMLY114514楼主2024/6/6 15:10

前面的IO直接折叠起来就行了

#include<bits/stdc++.h>
using namespace std;
namespace IO{
#define ischar(ch) (32<ch&&ch<127)
#define SIZE 1<<18
	char ibuf[SIZE],*is=ibuf,*it=ibuf;
#define getchar() (is==it&&(it=(is=ibuf)+fread(ibuf,1,SIZE,stdin),is==it)?EOF:*is++)
	template<typename Type>
	inline void dread(Type &a){
		Type x=0.0,t=1.0;
		int y=0,ch=getchar();
		while(!isdigit(ch)&&ch!=EOF)y|=(ch=='-'),ch=getchar();
		while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
		x=y?-x:x;
		if(ch^'.')return (void)(a=x);
		ch=getchar();
		while(isdigit(ch))x=x*10+(ch^48),ch=getchar(),t/=10;
		a=x*t;
	}
	inline void sread(string &a){
		a="";char ch;
		while(!ischar(ch)&&(ch^EOF))ch=getchar();
		while(ischar(ch))a+=ch,ch=getchar();
	}
	template<typename Type>
	inline void Aread(Type a[]){
		Type *pos=a;
		int ch=getchar();
		while(!ischar(ch)&&(ch^EOF))ch=getchar();
		while(ischar(ch))*pos++=ch,ch=getchar();
		*pos=0;
	}
	template<typename Type>
	inline void readchar(Type &a){
		int ch=getchar();
		while(!ischar(ch)&&(ch^EOF))ch=getchar();
		a=ch;
	}
	template<typename Type>
	inline void get(Type &a){
		int ch=getchar();
		while(!isdigit(ch)&&(ch^EOF))ch=getchar();
		a=(ch^48);
	}
	template<typename Type>
	inline void read(Type &a){
		Type x=0;int y=0,ch=getchar();
		while(!isdigit(ch)&&(ch^EOF))y|=(ch=='-'),ch=getchar();
		while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
		a=y?-x:x;
	}
	char obuf[SIZE],*op=obuf;
	inline void putch(const char &c){
		if(op-obuf==SIZE)fwrite(obuf,1,op-obuf,stdout),op=obuf;
		*op++=c;
	}
	template<typename Type>
	inline void write(Type x,int a){
		if(x<0)putch('-'),x=-x;
		static int s[35],top;top=0;
		do s[top++]=x%10,x/=10;
		while(x);
		while(top)putch(s[--top]+'0');
		if(~a)putch(a);
	}
	inline void oclear(){fwrite(obuf,1,op-obuf,stdout);}
#undef SIZE
#undef ischar
}
using namespace IO;
#define int long long
#define N 2010
int n,k[N],x[N],y[N],m,fa[N],siz[N],ans,cnt,top,st[N],etop;
struct{
	int u,v;
}res[N];
struct edge{
	int u,v,w;
}e[N*N];
#define add(u,v,w) e[++m]={u,v,w};
#define dis(i,j) (abs(x[i]-x[j])+abs(y[i]-y[j]))
inline int find(int x){
	while(fa[x]^x)x=fa[x]=fa[fa[x]];
	return x;
}
inline void merge(int x,int y){
	x=find(x);y=find(y);
	if(x==y)return;
	if(siz[x]>siz[y])swap(x,y);
	fa[x]=y;siz[y]+=siz[x];
}//按秩合并
inline int cmp(edge a,edge b){return a.w<b.w;}
signed main(){
	read(n);
	for(int i=1;i<=n;++i)read(x[i]),read(y[i]);
	for(int i=1,c;i<=n;++i)read(c),add(0,i,c);
	for(int i=1;i<=n;++i)read(k[i]);
	for(int i=1;i<=n;++i)
		for(int j=1;j<i;++j)
			add(i,j,(k[i]+k[j])*dis(i,j));
	for(int i=0;i<=n;++i)fa[i]=i,siz[i]=1;
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;++i){
		int u=find(e[i].u),v=find(e[i].v);
		if(u^v){
			ans+=e[i].w;
			merge(u,v);
			if(!e[i].u)st[++top]=v;
			else res[++etop]={e[i].u,e[i].v};
			if(++cnt==n)break;
		}
	}
	write(ans,'\n');
	write(top,'\n');
	while(top)write(st[top--],' ');
	putch('\n');write(etop,'\n');
	while(etop)write(res[etop].u,' '),write(res[etop--].v,'\n');
	oclear();
	return 0;
} 
2024/6/6 15:10
加载中...