Spanning tree, 2019NOI gold camp 6, good thinking


Because this competition ran into a problem, I used my memory to write this problem slowly. (what we did on site is really strong


Let's consider to build the edge from 1 to n first. If there are already n-1 black or white edges, then the output will be direct.

Otherwise, there is a point where both sides are black and white.

You can directly ask the edge of the point connecting the two sides and directly build this edge. Then you can go to the current point no matter whether it is a white tree or a black tree outside.

Next, we take the two points next to this point and search deeply. If the two points next to one of them are not connected, it must be a black edge and a white edge. Then we keep asking until they are connected.

In this process, we can use the linked list to maintain the left and right points.

using namespace std;

int n,m,tot1,tot2;
map<pair<int,int>,int> f;
long long X,Y,Z;
long long p[500010];
int w[500010],b[500010];
struct edge{
	int x,y;
int las[500010],nex[500010];

int ask_edge(int a,int b){
	if(f[make_pair(a,b)]) return f[make_pair(a,b)];
	if((min(a,b)*X+max(a,b)*Y)%Z<(p[a]+p[b])) return 2;
	else return 1;

int findpa(int*f,int x){
	if(f[x]!=x) return f[x]=findpa(f,f[x]);
	return x;

void update(int x,int y,int t){
	if(t==1) b[findpa(b,x)]=findpa(b,y),blk[++tot1]=(edge){x,y};
	else w[findpa(w,x)]=findpa(w,y),wht[++tot2]=(edge){x,y};

bool insame(int x,int y){
	int fx=findpa(w,x),fy=findpa(w,y);
	if(fx==fy) return true;
	if(fx==fy) return true;
	return false;

void dfs(int l,int r){
	if(!insame(las[l],r)) update(las[l],r,ask_edge(las[l],r)),nex[las[l]]=r,las[r]=las[l],dfs(las[l],r);
	else if(!insame(l,nex[r])) update(l,nex[r],ask_edge(l,nex[r])),nex[l]=nex[r],las[nex[r]]=l,dfs(l,nex[r]);

int main(){
	scanf("%d %d",&n,&m);
	int x,y,c;
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&x,&y,&c);
		if(c==0) c=2;
	scanf("%lld %lld %lld",&X,&Y,&Z);
	for(int i=1;i<=n;i++) scanf("%lld",&p[i]);
	for(int i=1;i<=n;i++) b[i]=w[i]=i;
	las[1]=n;for(int i=2;i<=n;i++) las[i]=i-1;
	nex[n]=1;for(int i=1;i<n;i++) nex[i]=i+1;
	for(int i=1;i<=n;i++) update(las[i],i,ask_edge(las[i],i));
	if(tot1>=n-1) for(int i=1;i<=n-1;i++) printf("%d %d\n",blk[i].x,blk[i].y);
	else if(tot2>=n-1) for(int i=1;i<=n-1;i++) printf("%d %d\n",wht[i].x,wht[i].y);
	if(tot1>=n-1 || tot2>=n-1) return 0;
	for(int i=1;i<=n;i++){
		if(insame(las[i],nex[i])) continue;
		if(tot1==n-1 || tot2==n-1) break;
	if(tot1>=n-1) for(int i=1;i<=n-1;i++) printf("%d %d\n",blk[i].x,blk[i].y);
	else if(tot2>=n-1) for(int i=1;i<=n-1;i++) printf("%d %d\n",wht[i].x,wht[i].y);


Posted on Fri, 01 Nov 2019 16:30:58 -0700 by meanrat