oj.uz

Submission #768719

# Submission time Handle Problem Language Result Execution time Memory
768719 2023-06-28T13:54:34 Z NintsiChkhaidze Team Contest (JOI22_team) C++17
0 / 100
 70 ms 119548 KB 
#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];
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++){
			mx[j] = *st[j].rbegin();
			st[j].erase(--st[j].end());
		}
		
		for (int j = 1; j <= 3; j++){
			for (int p: v[j][mx[j]]){
				if (!fix[p]){
					cnt[p] = 0;
					if (x[p] == mx[1]) ++cnt[p];
					if (y[p] == mx[2]) ++cnt[p];
					if (z[p] == mx[3]) ++cnt[p];
					if (cnt[p] >= 2) {
						fix[p] = 1;
						q.push(p);
					}
				}
			}
		}
	}
	
	cout<<rev[mx[1]] + rev[mx[2]] + rev[mx[3]];
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 58964 KB Output is correct
2 Runtime error 70 ms 119536 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 58964 KB Output is correct
2 Runtime error 70 ms 119536 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 58960 KB Output is correct
2 Runtime error 70 ms 119548 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 58960 KB Output is correct
2 Runtime error 70 ms 119548 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 58960 KB Output is correct
2 Runtime error 70 ms 119548 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 58960 KB Output is correct
2 Runtime error 70 ms 119548 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 58964 KB Output is correct
2 Runtime error 70 ms 119536 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -