oj.uz

Submission #847153

# Submission time Handle Problem Language Result Execution time Memory
847153 2023-09-09T08:46:20 Z errorgorn Security Guard (JOI23_guard) C++17
37 / 100
 197 ms 42148 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ll long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl
 
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
 
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
 
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
 
int n,m,k;
int arr[200005];
set<ii> al[200005];
 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>m>>k;
	rep(x,1,n+1) cin>>arr[x];
	
	int ans=0;
	rep(x,0,m){
		int a,b; cin>>a>>b;
		if (ii(arr[a],a)>ii(arr[b],b)) swap(a,b);
		al[a].insert({arr[b],b});
		ans+=arr[a];
	}
	
	vector<int> idx;
	rep(x,1,n+1) idx.pub(x);
	
	sort(all(idx),[](int i,int j){
		return ii(arr[i],i)<ii(arr[j],j);
	});
	
	idx.pob();
	for (auto u:idx){
		int v=(*al[u].begin()).se;
		
		ans+=arr[v]-arr[u];
		al[u].erase(al[u].begin());
		
		if (sz(al[u])>sz(al[v])) swap(al[u],al[v]);
		for (auto it:al[u]) al[v].insert(it);
	}
	
	cout<<ans<<endl;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 67 ms 26052 KB Output is correct
3 Correct 52 ms 26056 KB Output is correct
4 Correct 68 ms 25904 KB Output is correct
5 Correct 66 ms 26056 KB Output is correct
6 Correct 66 ms 26052 KB Output is correct
7 Correct 68 ms 25992 KB Output is correct
8 Correct 2 ms 10840 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 67 ms 26052 KB Output is correct
3 Correct 52 ms 26056 KB Output is correct
4 Correct 68 ms 25904 KB Output is correct
5 Correct 66 ms 26056 KB Output is correct
6 Correct 66 ms 26052 KB Output is correct
7 Correct 68 ms 25992 KB Output is correct
8 Correct 2 ms 10840 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 119 ms 30584 KB Output is correct
11 Correct 62 ms 30696 KB Output is correct
12 Correct 60 ms 30408 KB Output is correct
13 Correct 59 ms 30392 KB Output is correct
14 Correct 153 ms 30404 KB Output is correct
15 Correct 118 ms 30532 KB Output is correct
16 Correct 120 ms 30548 KB Output is correct
17 Correct 130 ms 30408 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 67 ms 26052 KB Output is correct
3 Correct 52 ms 26056 KB Output is correct
4 Correct 68 ms 25904 KB Output is correct
5 Correct 66 ms 26056 KB Output is correct
6 Correct 66 ms 26052 KB Output is correct
7 Correct 68 ms 25992 KB Output is correct
8 Correct 2 ms 10840 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 119 ms 30584 KB Output is correct
11 Correct 62 ms 30696 KB Output is correct
12 Correct 60 ms 30408 KB Output is correct
13 Correct 59 ms 30392 KB Output is correct
14 Correct 153 ms 30404 KB Output is correct
15 Correct 118 ms 30532 KB Output is correct
16 Correct 120 ms 30548 KB Output is correct
17 Correct 130 ms 30408 KB Output is correct
18 Correct 2 ms 10840 KB Output is correct
19 Correct 161 ms 30800 KB Output is correct
20 Correct 142 ms 30380 KB Output is correct
21 Correct 144 ms 30404 KB Output is correct
22 Correct 174 ms 30404 KB Output is correct
23 Correct 158 ms 30404 KB Output is correct
24 Correct 163 ms 30388 KB Output is correct
25 Correct 181 ms 31976 KB Output is correct
26 Correct 138 ms 30340 KB Output is correct
27 Correct 118 ms 30272 KB Output is correct
28 Correct 150 ms 30420 KB Output is correct
29 Correct 133 ms 30404 KB Output is correct
30 Correct 131 ms 30492 KB Output is correct
31 Correct 111 ms 30660 KB Output is correct
32 Correct 164 ms 30404 KB Output is correct
33 Correct 110 ms 29964 KB Output is correct
34 Correct 197 ms 42148 KB Output is correct
35 Correct 167 ms 35772 KB Output is correct
36 Correct 146 ms 30684 KB Output is correct
37 Correct 147 ms 30660 KB Output is correct
38 Correct 116 ms 30404 KB Output is correct
39 Correct 131 ms 30148 KB Output is correct
40 Correct 125 ms 30152 KB Output is correct
41 Correct 104 ms 29892 KB Output is correct
42 Correct 123 ms 29900 KB Output is correct
43 Correct 134 ms 30288 KB Output is correct
44 Correct 166 ms 30404 KB Output is correct
45 Correct 131 ms 30672 KB Output is correct
46 Correct 146 ms 30600 KB Output is correct
47 Correct 164 ms 30504 KB Output is correct
48 Correct 154 ms 30408 KB Output is correct
49 Correct 156 ms 31424 KB Output is correct
50 Correct 118 ms 30580 KB Output is correct
51 Correct 121 ms 30660 KB Output is correct
52 Correct 111 ms 28868 KB Output is correct

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 67 ms 26052 KB Output is correct
3 Correct 52 ms 26056 KB Output is correct
4 Correct 68 ms 25904 KB Output is correct
5 Correct 66 ms 26056 KB Output is correct
6 Correct 66 ms 26052 KB Output is correct
7 Correct 68 ms 25992 KB Output is correct
8 Correct 2 ms 10840 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 119 ms 30584 KB Output is correct
11 Correct 62 ms 30696 KB Output is correct
12 Correct 60 ms 30408 KB Output is correct
13 Correct 59 ms 30392 KB Output is correct
14 Correct 153 ms 30404 KB Output is correct
15 Correct 118 ms 30532 KB Output is correct
16 Correct 120 ms 30548 KB Output is correct
17 Correct 130 ms 30408 KB Output is correct
18 Correct 2 ms 10840 KB Output is correct
19 Correct 161 ms 30800 KB Output is correct
20 Correct 142 ms 30380 KB Output is correct
21 Correct 144 ms 30404 KB Output is correct
22 Correct 174 ms 30404 KB Output is correct
23 Correct 158 ms 30404 KB Output is correct
24 Correct 163 ms 30388 KB Output is correct
25 Correct 181 ms 31976 KB Output is correct
26 Correct 138 ms 30340 KB Output is correct
27 Correct 118 ms 30272 KB Output is correct
28 Correct 150 ms 30420 KB Output is correct
29 Correct 133 ms 30404 KB Output is correct
30 Correct 131 ms 30492 KB Output is correct
31 Correct 111 ms 30660 KB Output is correct
32 Correct 164 ms 30404 KB Output is correct
33 Correct 110 ms 29964 KB Output is correct
34 Correct 197 ms 42148 KB Output is correct
35 Correct 167 ms 35772 KB Output is correct
36 Correct 146 ms 30684 KB Output is correct
37 Correct 147 ms 30660 KB Output is correct
38 Correct 116 ms 30404 KB Output is correct
39 Correct 131 ms 30148 KB Output is correct
40 Correct 125 ms 30152 KB Output is correct
41 Correct 104 ms 29892 KB Output is correct
42 Correct 123 ms 29900 KB Output is correct
43 Correct 134 ms 30288 KB Output is correct
44 Correct 166 ms 30404 KB Output is correct
45 Correct 131 ms 30672 KB Output is correct
46 Correct 146 ms 30600 KB Output is correct
47 Correct 164 ms 30504 KB Output is correct
48 Correct 154 ms 30408 KB Output is correct
49 Correct 156 ms 31424 KB Output is correct
50 Correct 118 ms 30580 KB Output is correct
51 Correct 121 ms 30660 KB Output is correct
52 Correct 111 ms 28868 KB Output is correct
53 Incorrect 2 ms 10840 KB Output isn't correct
54 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Incorrect 2 ms 10840 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Incorrect 2 ms 10840 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 67 ms 26052 KB Output is correct
3 Correct 52 ms 26056 KB Output is correct
4 Correct 68 ms 25904 KB Output is correct
5 Correct 66 ms 26056 KB Output is correct
6 Correct 66 ms 26052 KB Output is correct
7 Correct 68 ms 25992 KB Output is correct
8 Correct 2 ms 10840 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 119 ms 30584 KB Output is correct
11 Correct 62 ms 30696 KB Output is correct
12 Correct 60 ms 30408 KB Output is correct
13 Correct 59 ms 30392 KB Output is correct
14 Correct 153 ms 30404 KB Output is correct
15 Correct 118 ms 30532 KB Output is correct
16 Correct 120 ms 30548 KB Output is correct
17 Correct 130 ms 30408 KB Output is correct
18 Correct 2 ms 10840 KB Output is correct
19 Correct 161 ms 30800 KB Output is correct
20 Correct 142 ms 30380 KB Output is correct
21 Correct 144 ms 30404 KB Output is correct
22 Correct 174 ms 30404 KB Output is correct
23 Correct 158 ms 30404 KB Output is correct
24 Correct 163 ms 30388 KB Output is correct
25 Correct 181 ms 31976 KB Output is correct
26 Correct 138 ms 30340 KB Output is correct
27 Correct 118 ms 30272 KB Output is correct
28 Correct 150 ms 30420 KB Output is correct
29 Correct 133 ms 30404 KB Output is correct
30 Correct 131 ms 30492 KB Output is correct
31 Correct 111 ms 30660 KB Output is correct
32 Correct 164 ms 30404 KB Output is correct
33 Correct 110 ms 29964 KB Output is correct
34 Correct 197 ms 42148 KB Output is correct
35 Correct 167 ms 35772 KB Output is correct
36 Correct 146 ms 30684 KB Output is correct
37 Correct 147 ms 30660 KB Output is correct
38 Correct 116 ms 30404 KB Output is correct
39 Correct 131 ms 30148 KB Output is correct
40 Correct 125 ms 30152 KB Output is correct
41 Correct 104 ms 29892 KB Output is correct
42 Correct 123 ms 29900 KB Output is correct
43 Correct 134 ms 30288 KB Output is correct
44 Correct 166 ms 30404 KB Output is correct
45 Correct 131 ms 30672 KB Output is correct
46 Correct 146 ms 30600 KB Output is correct
47 Correct 164 ms 30504 KB Output is correct
48 Correct 154 ms 30408 KB Output is correct
49 Correct 156 ms 31424 KB Output is correct
50 Correct 118 ms 30580 KB Output is correct
51 Correct 121 ms 30660 KB Output is correct
52 Correct 111 ms 28868 KB Output is correct
53 Incorrect 2 ms 10840 KB Output isn't correct
54 Halted 0 ms 0 KB -