oj.uz

Submission #768721

# Submission time Handle Problem Language Result Execution time Memory
768721 2023-06-28T13:57:45 Z NintsiChkhaidze Team Contest (JOI22_team) C++17
100 / 100
 720 ms 125360 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]++;
					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 25 ms 58964 KB Output is correct
2 Correct 24 ms 59056 KB Output is correct
3 Correct 24 ms 59080 KB Output is correct
4 Correct 25 ms 59008 KB Output is correct
5 Correct 24 ms 59012 KB Output is correct
6 Correct 26 ms 58996 KB Output is correct
7 Correct 25 ms 59072 KB Output is correct
8 Correct 25 ms 59080 KB Output is correct
9 Correct 24 ms 58996 KB Output is correct
10 Correct 24 ms 58968 KB Output is correct
11 Correct 24 ms 59084 KB Output is correct
12 Correct 25 ms 59016 KB Output is correct
13 Correct 25 ms 59060 KB Output is correct
14 Correct 24 ms 59092 KB Output is correct
15 Correct 23 ms 59156 KB Output is correct
16 Correct 25 ms 59052 KB Output is correct
17 Correct 23 ms 59080 KB Output is correct
18 Correct 25 ms 59160 KB Output is correct
19 Correct 26 ms 59156 KB Output is correct
20 Correct 25 ms 59120 KB Output is correct
21 Correct 25 ms 59092 KB Output is correct
22 Correct 24 ms 59096 KB Output is correct
23 Correct 24 ms 59072 KB Output is correct
24 Correct 24 ms 59068 KB Output is correct
25 Correct 25 ms 59032 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 58964 KB Output is correct
2 Correct 24 ms 59056 KB Output is correct
3 Correct 24 ms 59080 KB Output is correct
4 Correct 25 ms 59008 KB Output is correct
5 Correct 24 ms 59012 KB Output is correct
6 Correct 26 ms 58996 KB Output is correct
7 Correct 25 ms 59072 KB Output is correct
8 Correct 25 ms 59080 KB Output is correct
9 Correct 24 ms 58996 KB Output is correct
10 Correct 24 ms 58968 KB Output is correct
11 Correct 24 ms 59084 KB Output is correct
12 Correct 25 ms 59016 KB Output is correct
13 Correct 25 ms 59060 KB Output is correct
14 Correct 24 ms 59092 KB Output is correct
15 Correct 23 ms 59156 KB Output is correct
16 Correct 25 ms 59052 KB Output is correct
17 Correct 23 ms 59080 KB Output is correct
18 Correct 25 ms 59160 KB Output is correct
19 Correct 26 ms 59156 KB Output is correct
20 Correct 25 ms 59120 KB Output is correct
21 Correct 25 ms 59092 KB Output is correct
22 Correct 24 ms 59096 KB Output is correct
23 Correct 24 ms 59072 KB Output is correct
24 Correct 24 ms 59068 KB Output is correct
25 Correct 25 ms 59032 KB Output is correct
26 Correct 31 ms 60708 KB Output is correct
27 Correct 33 ms 60316 KB Output is correct
28 Correct 30 ms 60276 KB Output is correct
29 Correct 31 ms 60184 KB Output is correct
30 Correct 27 ms 59772 KB Output is correct
31 Correct 28 ms 59860 KB Output is correct
32 Correct 29 ms 59752 KB Output is correct
33 Correct 35 ms 59932 KB Output is correct
34 Correct 31 ms 60660 KB Output is correct
35 Correct 24 ms 59220 KB Output is correct
36 Correct 26 ms 59248 KB Output is correct
37 Correct 28 ms 59944 KB Output is correct
38 Correct 35 ms 59888 KB Output is correct
39 Correct 26 ms 59392 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 59084 KB Output is correct
2 Correct 24 ms 58964 KB Output is correct
3 Correct 24 ms 59016 KB Output is correct
4 Correct 27 ms 58956 KB Output is correct
5 Correct 24 ms 58984 KB Output is correct
6 Correct 24 ms 58956 KB Output is correct
7 Correct 25 ms 59072 KB Output is correct
8 Correct 30 ms 58964 KB Output is correct
9 Correct 29 ms 59064 KB Output is correct
10 Correct 24 ms 59072 KB Output is correct
11 Correct 172 ms 86492 KB Output is correct
12 Correct 137 ms 77292 KB Output is correct
13 Correct 134 ms 81620 KB Output is correct
14 Correct 215 ms 86480 KB Output is correct
15 Correct 161 ms 86964 KB Output is correct
16 Correct 119 ms 86908 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 59084 KB Output is correct
2 Correct 24 ms 58964 KB Output is correct
3 Correct 24 ms 59016 KB Output is correct
4 Correct 27 ms 58956 KB Output is correct
5 Correct 24 ms 58984 KB Output is correct
6 Correct 24 ms 58956 KB Output is correct
7 Correct 25 ms 59072 KB Output is correct
8 Correct 30 ms 58964 KB Output is correct
9 Correct 29 ms 59064 KB Output is correct
10 Correct 24 ms 59072 KB Output is correct
11 Correct 172 ms 86492 KB Output is correct
12 Correct 137 ms 77292 KB Output is correct
13 Correct 134 ms 81620 KB Output is correct
14 Correct 215 ms 86480 KB Output is correct
15 Correct 161 ms 86964 KB Output is correct
16 Correct 119 ms 86908 KB Output is correct
17 Correct 23 ms 58964 KB Output is correct
18 Correct 24 ms 59076 KB Output is correct
19 Correct 25 ms 59060 KB Output is correct
20 Correct 24 ms 59028 KB Output is correct
21 Correct 30 ms 59436 KB Output is correct
22 Correct 196 ms 86476 KB Output is correct
23 Correct 195 ms 85904 KB Output is correct
24 Correct 168 ms 79024 KB Output is correct
25 Correct 252 ms 86564 KB Output is correct
26 Correct 170 ms 86984 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 59084 KB Output is correct
2 Correct 24 ms 58964 KB Output is correct
3 Correct 24 ms 59016 KB Output is correct
4 Correct 27 ms 58956 KB Output is correct
5 Correct 24 ms 58984 KB Output is correct
6 Correct 24 ms 58956 KB Output is correct
7 Correct 25 ms 59072 KB Output is correct
8 Correct 30 ms 58964 KB Output is correct
9 Correct 29 ms 59064 KB Output is correct
10 Correct 24 ms 59072 KB Output is correct
11 Correct 172 ms 86492 KB Output is correct
12 Correct 137 ms 77292 KB Output is correct
13 Correct 134 ms 81620 KB Output is correct
14 Correct 215 ms 86480 KB Output is correct
15 Correct 161 ms 86964 KB Output is correct
16 Correct 119 ms 86908 KB Output is correct
17 Correct 23 ms 58964 KB Output is correct
18 Correct 24 ms 59076 KB Output is correct
19 Correct 25 ms 59060 KB Output is correct
20 Correct 24 ms 59028 KB Output is correct
21 Correct 30 ms 59436 KB Output is correct
22 Correct 196 ms 86476 KB Output is correct
23 Correct 195 ms 85904 KB Output is correct
24 Correct 168 ms 79024 KB Output is correct
25 Correct 252 ms 86564 KB Output is correct
26 Correct 170 ms 86984 KB Output is correct
27 Correct 25 ms 59068 KB Output is correct
28 Correct 24 ms 59148 KB Output is correct
29 Correct 25 ms 59144 KB Output is correct
30 Correct 24 ms 59140 KB Output is correct
31 Correct 28 ms 59744 KB Output is correct
32 Correct 24 ms 59248 KB Output is correct
33 Correct 26 ms 59180 KB Output is correct
34 Correct 258 ms 85108 KB Output is correct
35 Correct 272 ms 84816 KB Output is correct
36 Correct 304 ms 87116 KB Output is correct
37 Correct 338 ms 86888 KB Output is correct
38 Correct 236 ms 86576 KB Output is correct
39 Correct 121 ms 75892 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 59084 KB Output is correct
2 Correct 24 ms 58964 KB Output is correct
3 Correct 24 ms 59016 KB Output is correct
4 Correct 27 ms 58956 KB Output is correct
5 Correct 24 ms 58984 KB Output is correct
6 Correct 24 ms 58956 KB Output is correct
7 Correct 25 ms 59072 KB Output is correct
8 Correct 30 ms 58964 KB Output is correct
9 Correct 29 ms 59064 KB Output is correct
10 Correct 24 ms 59072 KB Output is correct
11 Correct 172 ms 86492 KB Output is correct
12 Correct 137 ms 77292 KB Output is correct
13 Correct 134 ms 81620 KB Output is correct
14 Correct 215 ms 86480 KB Output is correct
15 Correct 161 ms 86964 KB Output is correct
16 Correct 119 ms 86908 KB Output is correct
17 Correct 23 ms 58964 KB Output is correct
18 Correct 24 ms 59076 KB Output is correct
19 Correct 25 ms 59060 KB Output is correct
20 Correct 24 ms 59028 KB Output is correct
21 Correct 30 ms 59436 KB Output is correct
22 Correct 196 ms 86476 KB Output is correct
23 Correct 195 ms 85904 KB Output is correct
24 Correct 168 ms 79024 KB Output is correct
25 Correct 252 ms 86564 KB Output is correct
26 Correct 170 ms 86984 KB Output is correct
27 Correct 25 ms 59068 KB Output is correct
28 Correct 24 ms 59148 KB Output is correct
29 Correct 25 ms 59144 KB Output is correct
30 Correct 24 ms 59140 KB Output is correct
31 Correct 28 ms 59744 KB Output is correct
32 Correct 24 ms 59248 KB Output is correct
33 Correct 26 ms 59180 KB Output is correct
34 Correct 258 ms 85108 KB Output is correct
35 Correct 272 ms 84816 KB Output is correct
36 Correct 304 ms 87116 KB Output is correct
37 Correct 338 ms 86888 KB Output is correct
38 Correct 236 ms 86576 KB Output is correct
39 Correct 121 ms 75892 KB Output is correct
40 Correct 28 ms 59732 KB Output is correct
41 Correct 29 ms 59900 KB Output is correct
42 Correct 31 ms 59860 KB Output is correct
43 Correct 30 ms 59872 KB Output is correct
44 Correct 317 ms 87400 KB Output is correct
45 Correct 485 ms 87704 KB Output is correct
46 Correct 381 ms 89768 KB Output is correct
47 Correct 464 ms 89864 KB Output is correct
48 Correct 235 ms 89596 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 58964 KB Output is correct
2 Correct 24 ms 59056 KB Output is correct
3 Correct 24 ms 59080 KB Output is correct
4 Correct 25 ms 59008 KB Output is correct
5 Correct 24 ms 59012 KB Output is correct
6 Correct 26 ms 58996 KB Output is correct
7 Correct 25 ms 59072 KB Output is correct
8 Correct 25 ms 59080 KB Output is correct
9 Correct 24 ms 58996 KB Output is correct
10 Correct 24 ms 58968 KB Output is correct
11 Correct 24 ms 59084 KB Output is correct
12 Correct 25 ms 59016 KB Output is correct
13 Correct 25 ms 59060 KB Output is correct
14 Correct 24 ms 59092 KB Output is correct
15 Correct 23 ms 59156 KB Output is correct
16 Correct 25 ms 59052 KB Output is correct
17 Correct 23 ms 59080 KB Output is correct
18 Correct 25 ms 59160 KB Output is correct
19 Correct 26 ms 59156 KB Output is correct
20 Correct 25 ms 59120 KB Output is correct
21 Correct 25 ms 59092 KB Output is correct
22 Correct 24 ms 59096 KB Output is correct
23 Correct 24 ms 59072 KB Output is correct
24 Correct 24 ms 59068 KB Output is correct
25 Correct 25 ms 59032 KB Output is correct
26 Correct 31 ms 60708 KB Output is correct
27 Correct 33 ms 60316 KB Output is correct
28 Correct 30 ms 60276 KB Output is correct
29 Correct 31 ms 60184 KB Output is correct
30 Correct 27 ms 59772 KB Output is correct
31 Correct 28 ms 59860 KB Output is correct
32 Correct 29 ms 59752 KB Output is correct
33 Correct 35 ms 59932 KB Output is correct
34 Correct 31 ms 60660 KB Output is correct
35 Correct 24 ms 59220 KB Output is correct
36 Correct 26 ms 59248 KB Output is correct
37 Correct 28 ms 59944 KB Output is correct
38 Correct 35 ms 59888 KB Output is correct
39 Correct 26 ms 59392 KB Output is correct
40 Correct 24 ms 59084 KB Output is correct
41 Correct 24 ms 58964 KB Output is correct
42 Correct 24 ms 59016 KB Output is correct
43 Correct 27 ms 58956 KB Output is correct
44 Correct 24 ms 58984 KB Output is correct
45 Correct 24 ms 58956 KB Output is correct
46 Correct 25 ms 59072 KB Output is correct
47 Correct 30 ms 58964 KB Output is correct
48 Correct 29 ms 59064 KB Output is correct
49 Correct 24 ms 59072 KB Output is correct
50 Correct 172 ms 86492 KB Output is correct
51 Correct 137 ms 77292 KB Output is correct
52 Correct 134 ms 81620 KB Output is correct
53 Correct 215 ms 86480 KB Output is correct
54 Correct 161 ms 86964 KB Output is correct
55 Correct 119 ms 86908 KB Output is correct
56 Correct 23 ms 58964 KB Output is correct
57 Correct 24 ms 59076 KB Output is correct
58 Correct 25 ms 59060 KB Output is correct
59 Correct 24 ms 59028 KB Output is correct
60 Correct 30 ms 59436 KB Output is correct
61 Correct 196 ms 86476 KB Output is correct
62 Correct 195 ms 85904 KB Output is correct
63 Correct 168 ms 79024 KB Output is correct
64 Correct 252 ms 86564 KB Output is correct
65 Correct 170 ms 86984 KB Output is correct
66 Correct 25 ms 59068 KB Output is correct
67 Correct 24 ms 59148 KB Output is correct
68 Correct 25 ms 59144 KB Output is correct
69 Correct 24 ms 59140 KB Output is correct
70 Correct 28 ms 59744 KB Output is correct
71 Correct 24 ms 59248 KB Output is correct
72 Correct 26 ms 59180 KB Output is correct
73 Correct 258 ms 85108 KB Output is correct
74 Correct 272 ms 84816 KB Output is correct
75 Correct 304 ms 87116 KB Output is correct
76 Correct 338 ms 86888 KB Output is correct
77 Correct 236 ms 86576 KB Output is correct
78 Correct 121 ms 75892 KB Output is correct
79 Correct 28 ms 59732 KB Output is correct
80 Correct 29 ms 59900 KB Output is correct
81 Correct 31 ms 59860 KB Output is correct
82 Correct 30 ms 59872 KB Output is correct
83 Correct 317 ms 87400 KB Output is correct
84 Correct 485 ms 87704 KB Output is correct
85 Correct 381 ms 89768 KB Output is correct
86 Correct 464 ms 89864 KB Output is correct
87 Correct 235 ms 89596 KB Output is correct
88 Correct 720 ms 124556 KB Output is correct
89 Correct 646 ms 109032 KB Output is correct
90 Correct 618 ms 111544 KB Output is correct
91 Correct 647 ms 105568 KB Output is correct
92 Correct 535 ms 93024 KB Output is correct
93 Correct 664 ms 102860 KB Output is correct
94 Correct 590 ms 96468 KB Output is correct
95 Correct 339 ms 99580 KB Output is correct
96 Correct 551 ms 125360 KB Output is correct
97 Correct 134 ms 90924 KB Output is correct
98 Correct 214 ms 94160 KB Output is correct
99 Correct 246 ms 94968 KB Output is correct