Submission #768726

#	Time	Username	Problem	Language	Result	Execution time	Memory
768726		NintsiChkhaidze	Team Contest (JOI22_team)	C++17	100 / 100	696 ms	121520 KiB

team

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define s second
#define f first
#define left (node<<1),l,((l+r)>>1)
#define right ((node<<1)|1),((l+r)>>1) + 1,r
// #define int ll 
using namespace std;

const int N = 5e5 + 5;

bool f[N],fix[N];
int x[N],y[N],z[N],cnt[N],mx[6],mxold[6];
int d[3*N],rev[3*N];
map <int,int> mp;
multiset <int> st[5];
vector <int> v[5][N];

signed main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int n;
	cin>>n;
	
	int id=0;
	for (int i = 1; i <= n; i++){
		cin>>x[i]>>y[i]>>z[i];
		d[++id] = x[i];
		d[++id] = y[i];
		d[++id] = z[i];
		
	}
	sort(d+1,d+id+1);
	int val=0;
	for (int i = 1; i <= id; i++){
		if (i == 1 || d[i] != d[i - 1]) ++val;	
		mp[d[i]] = val;
		rev[val] = d[i];
	}
	
	for (int i = 1; i <= n; i++){
		x[i] = mp[x[i]];
		y[i] = mp[y[i]];
		z[i] = mp[z[i]];
		mx[1] = max(mx[1],x[i]);
		mx[2] = max(mx[2],y[i]);
		mx[3] = max(mx[3],z[i]);	
	}
	
	queue <int> q;
	for (int i = 1; i <= n; i++){
		if (x[i] == mx[1]) ++cnt[i];
		if (y[i] == mx[2]) ++cnt[i];
		if (z[i] == mx[3]) ++cnt[i];
		if (cnt[i] > 1) {
			q.push(i),fix[i]=1;	
		}
		
		v[1][x[i]].pb(i);
		v[2][y[i]].pb(i);
		v[3][z[i]].pb(i);
		st[1].insert(x[i]);
		st[2].insert(y[i]);
		st[3].insert(z[i]);
	}
	
	while (q.size()){
		int idx = q.front();
		q.pop();
		if (f[idx]) continue;
		
		f[idx] = 1;
		st[1].erase(st[1].find(x[idx]));
		st[2].erase(st[2].find(y[idx]));
		st[3].erase(st[3].find(z[idx]));
		
		if(st[1].size() == 0){
			cout<<-1;
			exit(0);
		}
		
		
		for (int j = 1; j <= 3; j++){
			mxold[j] = mx[j];
			mx[j] = *st[j].rbegin();
		}
		
		for (int j = 1; j <= 3; j++){
			if (mxold[j] == mx[j]) continue;
			for (int p: v[j][mx[j]]){
				if (!fix[p]){
					cnt[p] = 0;
			   		cnt[p] += (mx[1] == x[p]);
			   		cnt[p] += (mx[2] == y[p]);
			   		cnt[p] += (mx[3] == z[p]);
					if (cnt[p] >= 2) {
						fix[p] = 1;
						q.push(p);
					}
				}
			}
		}
	}
	
	cout<<rev[mx[1]] + rev[mx[2]] + rev[mx[3]];
}

• 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