Submission #30765929

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int Mt=1e5,N=1.5e5+10;
struct node{int x,y,z,id;}s[N];
int n,vis[N];
queue<int>qx,qy,qz;
inline char getc(){
	static char buf[Mt],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mt,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
	int r=0,f=1;char c=getc();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getc();}
	while(c<='9'&&c>='0') r=(r<<1)+(r<<3)+(c^48),c=getc();
	return r*f;
}
void put(int x){
	if(x<0){putchar('-');x=~x+1;}
	if(x>9) put(x/10);
	putchar(x%10+'0');
}
int cmpx(node x,node y){return x.x>y.x;}
int cmpy(node x,node y){return x.y>y.y;}
int cmpz(node x,node y){return x.z>y.z;}
int cmpid(node x,node y){return x.id<y.id;}
signed main(){
//	freopen("cpp.in","r",stdin);
//	freopen("cpp.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++) s[i].x=read(),s[i].y=read(),s[i].z=read(),s[i].id=i;
	sort(s+1,s+1+n,cmpx);
	for(int i=1;i<=n;i++) qx.push(s[i].id);
	sort(s+1,s+1+n,cmpy);
	for(int i=1;i<=n;i++) qy.push(s[i].id);
	sort(s+1,s+1+n,cmpz);
	for(int i=1;i<=n;i++) qz.push(s[i].id);
	sort(s+1,s+1+n,cmpid);
	while(1){
		if(qx.empty()||qy.empty()||qz.empty())return puts("-1"),0;
		while(vis[qx.front()])qx.pop();
		while(vis[qy.front()])qy.pop();
		while(vis[qz.front()])qz.pop();
		int hx=qx.front(),hy=qy.front(),hz=qz.front(),p=0;
		if(s[hx].y==s[hy].y||s[hx].z==s[hz].z) qx.pop(),vis[hx]=p=1;
		else if(s[hy].x==s[hx].x||s[hy].z==s[hz].z) qy.pop(),vis[hy]=p=1;
		else if(s[hz].x==s[hx].x||s[hz].y==s[hy].y) qz.pop(),vis[hz]=p=1;
		if(!p)break;
	}
	return put(s[qx.front()].x+s[qy.front()].y+s[qz.front()].z),puts(""),0;
}

Submission Info

Judge Result