oj.uz

Submission #768726

# Submission time Handle Problem Language Result Execution time Memory
768726 2023-06-28T14:00:36 Z NintsiChkhaidze Team Contest (JOI22_team) C++17
100 / 100
 696 ms 121520 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],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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 58964 KB Output is correct
2 Correct 30 ms 59052 KB Output is correct
3 Correct 25 ms 58980 KB Output is correct
4 Correct 25 ms 59076 KB Output is correct
5 Correct 27 ms 59004 KB Output is correct
6 Correct 25 ms 58976 KB Output is correct
7 Correct 23 ms 58964 KB Output is correct
8 Correct 25 ms 59024 KB Output is correct
9 Correct 24 ms 58980 KB Output is correct
10 Correct 23 ms 58964 KB Output is correct
11 Correct 24 ms 59084 KB Output is correct
12 Correct 25 ms 58964 KB Output is correct
13 Correct 25 ms 58996 KB Output is correct
14 Correct 24 ms 59192 KB Output is correct
15 Correct 26 ms 59220 KB Output is correct
16 Correct 28 ms 59172 KB Output is correct
17 Correct 25 ms 59168 KB Output is correct
18 Correct 25 ms 59124 KB Output is correct
19 Correct 24 ms 59068 KB Output is correct
20 Correct 25 ms 59084 KB Output is correct
21 Correct 24 ms 59120 KB Output is correct
22 Correct 24 ms 59092 KB Output is correct
23 Correct 25 ms 59040 KB Output is correct
24 Correct 28 ms 59048 KB Output is correct
25 Correct 25 ms 59092 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 58964 KB Output is correct
2 Correct 30 ms 59052 KB Output is correct
3 Correct 25 ms 58980 KB Output is correct
4 Correct 25 ms 59076 KB Output is correct
5 Correct 27 ms 59004 KB Output is correct
6 Correct 25 ms 58976 KB Output is correct
7 Correct 23 ms 58964 KB Output is correct
8 Correct 25 ms 59024 KB Output is correct
9 Correct 24 ms 58980 KB Output is correct
10 Correct 23 ms 58964 KB Output is correct
11 Correct 24 ms 59084 KB Output is correct
12 Correct 25 ms 58964 KB Output is correct
13 Correct 25 ms 58996 KB Output is correct
14 Correct 24 ms 59192 KB Output is correct
15 Correct 26 ms 59220 KB Output is correct
16 Correct 28 ms 59172 KB Output is correct
17 Correct 25 ms 59168 KB Output is correct
18 Correct 25 ms 59124 KB Output is correct
19 Correct 24 ms 59068 KB Output is correct
20 Correct 25 ms 59084 KB Output is correct
21 Correct 24 ms 59120 KB Output is correct
22 Correct 24 ms 59092 KB Output is correct
23 Correct 25 ms 59040 KB Output is correct
24 Correct 28 ms 59048 KB Output is correct
25 Correct 25 ms 59092 KB Output is correct
26 Correct 37 ms 60592 KB Output is correct
27 Correct 30 ms 60244 KB Output is correct
28 Correct 31 ms 60224 KB Output is correct
29 Correct 31 ms 60084 KB Output is correct
30 Correct 27 ms 59772 KB Output is correct
31 Correct 29 ms 59936 KB Output is correct
32 Correct 31 ms 59860 KB Output is correct
33 Correct 28 ms 59996 KB Output is correct
34 Correct 37 ms 60620 KB Output is correct
35 Correct 24 ms 59220 KB Output is correct
36 Correct 24 ms 59264 KB Output is correct
37 Correct 33 ms 59976 KB Output is correct
38 Correct 29 ms 59960 KB Output is correct
39 Correct 27 ms 59348 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 59092 KB Output is correct
2 Correct 24 ms 59084 KB Output is correct
3 Correct 24 ms 59036 KB Output is correct
4 Correct 24 ms 58952 KB Output is correct
5 Correct 24 ms 59068 KB Output is correct
6 Correct 24 ms 58984 KB Output is correct
7 Correct 24 ms 59032 KB Output is correct
8 Correct 24 ms 58956 KB Output is correct
9 Correct 24 ms 58964 KB Output is correct
10 Correct 24 ms 59032 KB Output is correct
11 Correct 178 ms 86516 KB Output is correct
12 Correct 150 ms 77380 KB Output is correct
13 Correct 120 ms 81548 KB Output is correct
14 Correct 219 ms 86588 KB Output is correct
15 Correct 158 ms 87008 KB Output is correct
16 Correct 113 ms 86944 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 59092 KB Output is correct
2 Correct 24 ms 59084 KB Output is correct
3 Correct 24 ms 59036 KB Output is correct
4 Correct 24 ms 58952 KB Output is correct
5 Correct 24 ms 59068 KB Output is correct
6 Correct 24 ms 58984 KB Output is correct
7 Correct 24 ms 59032 KB Output is correct
8 Correct 24 ms 58956 KB Output is correct
9 Correct 24 ms 58964 KB Output is correct
10 Correct 24 ms 59032 KB Output is correct
11 Correct 178 ms 86516 KB Output is correct
12 Correct 150 ms 77380 KB Output is correct
13 Correct 120 ms 81548 KB Output is correct
14 Correct 219 ms 86588 KB Output is correct
15 Correct 158 ms 87008 KB Output is correct
16 Correct 113 ms 86944 KB Output is correct
17 Correct 24 ms 58964 KB Output is correct
18 Correct 24 ms 59032 KB Output is correct
19 Correct 23 ms 59080 KB Output is correct
20 Correct 24 ms 59060 KB Output is correct
21 Correct 28 ms 59372 KB Output is correct
22 Correct 225 ms 86504 KB Output is correct
23 Correct 194 ms 85916 KB Output is correct
24 Correct 176 ms 79048 KB Output is correct
25 Correct 250 ms 86548 KB Output is correct
26 Correct 191 ms 86984 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 59092 KB Output is correct
2 Correct 24 ms 59084 KB Output is correct
3 Correct 24 ms 59036 KB Output is correct
4 Correct 24 ms 58952 KB Output is correct
5 Correct 24 ms 59068 KB Output is correct
6 Correct 24 ms 58984 KB Output is correct
7 Correct 24 ms 59032 KB Output is correct
8 Correct 24 ms 58956 KB Output is correct
9 Correct 24 ms 58964 KB Output is correct
10 Correct 24 ms 59032 KB Output is correct
11 Correct 178 ms 86516 KB Output is correct
12 Correct 150 ms 77380 KB Output is correct
13 Correct 120 ms 81548 KB Output is correct
14 Correct 219 ms 86588 KB Output is correct
15 Correct 158 ms 87008 KB Output is correct
16 Correct 113 ms 86944 KB Output is correct
17 Correct 24 ms 58964 KB Output is correct
18 Correct 24 ms 59032 KB Output is correct
19 Correct 23 ms 59080 KB Output is correct
20 Correct 24 ms 59060 KB Output is correct
21 Correct 28 ms 59372 KB Output is correct
22 Correct 225 ms 86504 KB Output is correct
23 Correct 194 ms 85916 KB Output is correct
24 Correct 176 ms 79048 KB Output is correct
25 Correct 250 ms 86548 KB Output is correct
26 Correct 191 ms 86984 KB Output is correct
27 Correct 27 ms 59104 KB Output is correct
28 Correct 24 ms 59088 KB Output is correct
29 Correct 24 ms 59092 KB Output is correct
30 Correct 24 ms 59060 KB Output is correct
31 Correct 29 ms 59804 KB Output is correct
32 Correct 25 ms 59192 KB Output is correct
33 Correct 25 ms 59248 KB Output is correct
34 Correct 265 ms 85080 KB Output is correct
35 Correct 278 ms 84868 KB Output is correct
36 Correct 297 ms 87116 KB Output is correct
37 Correct 330 ms 86748 KB Output is correct
38 Correct 199 ms 86580 KB Output is correct
39 Correct 130 ms 76008 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 59092 KB Output is correct
2 Correct 24 ms 59084 KB Output is correct
3 Correct 24 ms 59036 KB Output is correct
4 Correct 24 ms 58952 KB Output is correct
5 Correct 24 ms 59068 KB Output is correct
6 Correct 24 ms 58984 KB Output is correct
7 Correct 24 ms 59032 KB Output is correct
8 Correct 24 ms 58956 KB Output is correct
9 Correct 24 ms 58964 KB Output is correct
10 Correct 24 ms 59032 KB Output is correct
11 Correct 178 ms 86516 KB Output is correct
12 Correct 150 ms 77380 KB Output is correct
13 Correct 120 ms 81548 KB Output is correct
14 Correct 219 ms 86588 KB Output is correct
15 Correct 158 ms 87008 KB Output is correct
16 Correct 113 ms 86944 KB Output is correct
17 Correct 24 ms 58964 KB Output is correct
18 Correct 24 ms 59032 KB Output is correct
19 Correct 23 ms 59080 KB Output is correct
20 Correct 24 ms 59060 KB Output is correct
21 Correct 28 ms 59372 KB Output is correct
22 Correct 225 ms 86504 KB Output is correct
23 Correct 194 ms 85916 KB Output is correct
24 Correct 176 ms 79048 KB Output is correct
25 Correct 250 ms 86548 KB Output is correct
26 Correct 191 ms 86984 KB Output is correct
27 Correct 27 ms 59104 KB Output is correct
28 Correct 24 ms 59088 KB Output is correct
29 Correct 24 ms 59092 KB Output is correct
30 Correct 24 ms 59060 KB Output is correct
31 Correct 29 ms 59804 KB Output is correct
32 Correct 25 ms 59192 KB Output is correct
33 Correct 25 ms 59248 KB Output is correct
34 Correct 265 ms 85080 KB Output is correct
35 Correct 278 ms 84868 KB Output is correct
36 Correct 297 ms 87116 KB Output is correct
37 Correct 330 ms 86748 KB Output is correct
38 Correct 199 ms 86580 KB Output is correct
39 Correct 130 ms 76008 KB Output is correct
40 Correct 28 ms 59732 KB Output is correct
41 Correct 29 ms 59860 KB Output is correct
42 Correct 28 ms 59932 KB Output is correct
43 Correct 30 ms 59920 KB Output is correct
44 Correct 354 ms 87504 KB Output is correct
45 Correct 391 ms 87656 KB Output is correct
46 Correct 403 ms 87776 KB Output is correct
47 Correct 503 ms 87724 KB Output is correct
48 Correct 236 ms 87588 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 58964 KB Output is correct
2 Correct 30 ms 59052 KB Output is correct
3 Correct 25 ms 58980 KB Output is correct
4 Correct 25 ms 59076 KB Output is correct
5 Correct 27 ms 59004 KB Output is correct
6 Correct 25 ms 58976 KB Output is correct
7 Correct 23 ms 58964 KB Output is correct
8 Correct 25 ms 59024 KB Output is correct
9 Correct 24 ms 58980 KB Output is correct
10 Correct 23 ms 58964 KB Output is correct
11 Correct 24 ms 59084 KB Output is correct
12 Correct 25 ms 58964 KB Output is correct
13 Correct 25 ms 58996 KB Output is correct
14 Correct 24 ms 59192 KB Output is correct
15 Correct 26 ms 59220 KB Output is correct
16 Correct 28 ms 59172 KB Output is correct
17 Correct 25 ms 59168 KB Output is correct
18 Correct 25 ms 59124 KB Output is correct
19 Correct 24 ms 59068 KB Output is correct
20 Correct 25 ms 59084 KB Output is correct
21 Correct 24 ms 59120 KB Output is correct
22 Correct 24 ms 59092 KB Output is correct
23 Correct 25 ms 59040 KB Output is correct
24 Correct 28 ms 59048 KB Output is correct
25 Correct 25 ms 59092 KB Output is correct
26 Correct 37 ms 60592 KB Output is correct
27 Correct 30 ms 60244 KB Output is correct
28 Correct 31 ms 60224 KB Output is correct
29 Correct 31 ms 60084 KB Output is correct
30 Correct 27 ms 59772 KB Output is correct
31 Correct 29 ms 59936 KB Output is correct
32 Correct 31 ms 59860 KB Output is correct
33 Correct 28 ms 59996 KB Output is correct
34 Correct 37 ms 60620 KB Output is correct
35 Correct 24 ms 59220 KB Output is correct
36 Correct 24 ms 59264 KB Output is correct
37 Correct 33 ms 59976 KB Output is correct
38 Correct 29 ms 59960 KB Output is correct
39 Correct 27 ms 59348 KB Output is correct
40 Correct 24 ms 59092 KB Output is correct
41 Correct 24 ms 59084 KB Output is correct
42 Correct 24 ms 59036 KB Output is correct
43 Correct 24 ms 58952 KB Output is correct
44 Correct 24 ms 59068 KB Output is correct
45 Correct 24 ms 58984 KB Output is correct
46 Correct 24 ms 59032 KB Output is correct
47 Correct 24 ms 58956 KB Output is correct
48 Correct 24 ms 58964 KB Output is correct
49 Correct 24 ms 59032 KB Output is correct
50 Correct 178 ms 86516 KB Output is correct
51 Correct 150 ms 77380 KB Output is correct
52 Correct 120 ms 81548 KB Output is correct
53 Correct 219 ms 86588 KB Output is correct
54 Correct 158 ms 87008 KB Output is correct
55 Correct 113 ms 86944 KB Output is correct
56 Correct 24 ms 58964 KB Output is correct
57 Correct 24 ms 59032 KB Output is correct
58 Correct 23 ms 59080 KB Output is correct
59 Correct 24 ms 59060 KB Output is correct
60 Correct 28 ms 59372 KB Output is correct
61 Correct 225 ms 86504 KB Output is correct
62 Correct 194 ms 85916 KB Output is correct
63 Correct 176 ms 79048 KB Output is correct
64 Correct 250 ms 86548 KB Output is correct
65 Correct 191 ms 86984 KB Output is correct
66 Correct 27 ms 59104 KB Output is correct
67 Correct 24 ms 59088 KB Output is correct
68 Correct 24 ms 59092 KB Output is correct
69 Correct 24 ms 59060 KB Output is correct
70 Correct 29 ms 59804 KB Output is correct
71 Correct 25 ms 59192 KB Output is correct
72 Correct 25 ms 59248 KB Output is correct
73 Correct 265 ms 85080 KB Output is correct
74 Correct 278 ms 84868 KB Output is correct
75 Correct 297 ms 87116 KB Output is correct
76 Correct 330 ms 86748 KB Output is correct
77 Correct 199 ms 86580 KB Output is correct
78 Correct 130 ms 76008 KB Output is correct
79 Correct 28 ms 59732 KB Output is correct
80 Correct 29 ms 59860 KB Output is correct
81 Correct 28 ms 59932 KB Output is correct
82 Correct 30 ms 59920 KB Output is correct
83 Correct 354 ms 87504 KB Output is correct
84 Correct 391 ms 87656 KB Output is correct
85 Correct 403 ms 87776 KB Output is correct
86 Correct 503 ms 87724 KB Output is correct
87 Correct 236 ms 87588 KB Output is correct
88 Correct 696 ms 120632 KB Output is correct
89 Correct 674 ms 105124 KB Output is correct
90 Correct 653 ms 107636 KB Output is correct
91 Correct 643 ms 101680 KB Output is correct
92 Correct 458 ms 90592 KB Output is correct
93 Correct 588 ms 99952 KB Output is correct
94 Correct 567 ms 93960 KB Output is correct
95 Correct 349 ms 95668 KB Output is correct
96 Correct 578 ms 121520 KB Output is correct
97 Correct 135 ms 87000 KB Output is correct
98 Correct 225 ms 91684 KB Output is correct
99 Correct 281 ms 92636 KB Output is correct