Submission #551669

#	Time	Username	Problem	Language	Result	Execution time	Memory
551669		kshitij_sodani	Team Contest (JOI22_team)	C++14	100 / 100	1734 ms	729668 KiB

team

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
#define endl '\n'
const llo mod=1e9+7;
llo n;
llo it[200001][3];
multiset<llo> pre[3];
set<pair<llo,llo>> pre2[1500001][3][3];
llo ma[3];
llo vis[200001];
map<llo,llo> tt2[200001];
void remove(llo i){
	vis[i]=1;
	//cout<<i<<":"<<endl;
	for(llo j=0;j<3;j++){
		auto jj=pre[j].find(it[i][j]);
		pre[j].erase(jj);
	}
	/*for(int j=0;j<3;j++){
		for(auto i:pre[j]){
			cout<<i<<',';
		}
		cout<<endl;
	}*/
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;

	for(llo i=0;i<n;i++){
		for(llo j=0;j<3;j++){
			cin>>it[i][j];
			
		}
	}
	for(llo j=0;j<3;j++){
		map<llo,llo> ss;
		for(llo i=0;i<n;i++){
			ss[it[i][j]]++;
		}
		map<llo,llo> tt;
		llo ind=0;
		for(auto i:ss){
			tt[i.a]=ind;
			ind++;
		}
		for(llo i=0;i<n;i++){
			tt2[j][tt[it[i][j]]]=it[i][j];
			it[i][j]=tt[it[i][j]];
			pre[j].insert(it[i][j]);
		}
	}
	for(llo i=0;i<n;i++){
		for(llo j=0;j<3;j++){
			for(llo k=j+1;k<3;k++){
				pre2[it[i][j]][j][k].insert({it[i][k],i});
			}
		}
	}
	while(true){
		if(pre[0].size()<3){
			cout<<-1<<endl;
			return 0;
		}
		for(llo i=0;i<3;i++){
			auto j=pre[i].end();
			j--;
			ma[i]=(*j);
		}
		llo st=0;
		for(llo j=0;j<2;j++){
			for(llo k=j+1;k<3;k++){
				while(pre2[ma[j]][j][k].size()){
					auto jj=pre2[ma[j]][j][k].end();
					jj--;
					pair<llo,llo> no=(*jj);
					if(vis[no.b]==1){
						pre2[ma[j]][j][k].erase(jj);
						continue;
					}
					if(no.a==ma[k]){
						st++;
						vis[no.b]=1;
						remove(no.b);
						pre2[ma[j]][j][k].erase(jj);
						continue;
					}
					break;
				}
			}
		}
		if(st==0){
			llo su=0;
			for(int j=0;j<3;j++){
				su+=tt2[j][ma[j]];
			}
			cout<<su<<endl;
			return 0;
		}
	}
/*	while(true){
		if(pre[0].size()<3){
			cout<<-1<<endl;
			return 0;
		}
		for(llo i=0;i<3;i++){
			auto j=pre[i].end();
			j--;
			ma[i]=(*j);
		}
		llo st=0;
		for(llo i=0;i<n;i++){
			llo co=0;
			if(vis[i]){
				continue;
			}

			for(llo j=0;j<3;j++){
				if(it[i][j]==ma[j]){
					co++;
				}
			}
			if(co>1){
				for(llo j=0;j<3;j++){
					auto ii=pre[j].find(it[i][j]);
					pre[j].erase(ii);

				}
				vis[i]=1;
				st++;
			}
		}
		if(st==0){
			cout<<ma[0]+ma[2]+ma[1]<<endl;
			return 0;
		}
	}

*/





	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 27 / 27