oj.uz

Submission #893438

# Submission time Handle Problem Language Result Execution time Memory
893438 2023-12-27T04:53:57 Z vjudge1 Road Construction (JOI21_road_construction) C++17
11 / 100
 368 ms 25516 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
///*                                                    __                    __                        __                    */
///*        ======     _      /| /|  __   _            /   |  |   /|  |   @  |    |  |  | /   /| |\  | /   |  |  @ | /        */
///* \-       ||  |_| |_     / |/ | |  | |_  |-        |   |--|  /-|  |   |  \ \  |==|  |-   /=| | \ | |   |--|  | |-         */
///*          ||  | | |_    /     | |__|  _| |_        \__ |  | /  |  |__ |  __|  |  |  | \ /  | |  \| \__ |  |  | | \        */
///*  
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
void solve(){
	int n, k;
	cin >> n >> k;
	if(n*n < 1e9){
		vii v(n);
		vi ans;
		for(auto &[i,j]:v)cin >> i >> j;
		for(int i = 0; i < n; i++){
			for(int j = i+1; j < n; j++){
				ans.pb(abs(v[i].ff-v[j].ff)+abs(v[i].ss-v[j].ss));
			}
		}sort(all(ans));
		for(int i = 0; i < k; i++)cout << ans[i] << '\n';
	}else if(k == 1){
		
	}else{
		vii v(n);
		for(auto &[i, j]:v)cin >> i >> j;
		sort(all(v));
		multiset<pii> st;
		vi df, ans;
		for(int i = 0; i < n-1; i++){
			df.pb(abs(v[i].ff-v[i+1].ff)+abs(v[i].ss-v[i+1].ss));
		}
		for(int i = 0; i < n-1; i++){
			st.insert({df[i], i+1});
		}
		while((int)ans.size() < k){
			auto [cost, i] = *st.begin();
			st.erase(*st.begin());
			ans.pb(cost);
			if(i < n-1){
				st.insert({cost+df[i], i+1});
			}
		}
		sort(all(ans));
		for(int i = 0; i < k; i++){
			cout << ans[i] << '\n';
		}
	}
}
main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int test = 1;
	//~ cin >> test;
	while(test--){
		solve();
	}
}

Compilation message

road_construction.cpp:58:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   58 | main(){
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6948 KB Output is correct
2 Correct 52 ms 6840 KB Output is correct
3 Correct 38 ms 5052 KB Output is correct
4 Correct 34 ms 5060 KB Output is correct
5 Correct 50 ms 6092 KB Output is correct
6 Correct 17 ms 4556 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 25164 KB Output is correct
2 Correct 344 ms 25088 KB Output is correct
3 Correct 34 ms 4856 KB Output is correct
4 Correct 190 ms 25032 KB Output is correct
5 Correct 193 ms 25244 KB Output is correct
6 Correct 171 ms 25516 KB Output is correct
7 Correct 177 ms 24932 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6948 KB Output is correct
2 Correct 52 ms 6840 KB Output is correct
3 Correct 38 ms 5052 KB Output is correct
4 Correct 34 ms 5060 KB Output is correct
5 Correct 50 ms 6092 KB Output is correct
6 Correct 17 ms 4556 KB Output is correct
7 Incorrect 164 ms 13824 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6948 KB Output is correct
2 Correct 52 ms 6840 KB Output is correct
3 Correct 38 ms 5052 KB Output is correct
4 Correct 34 ms 5060 KB Output is correct
5 Correct 50 ms 6092 KB Output is correct
6 Correct 17 ms 4556 KB Output is correct
7 Correct 368 ms 25164 KB Output is correct
8 Correct 344 ms 25088 KB Output is correct
9 Correct 34 ms 4856 KB Output is correct
10 Correct 190 ms 25032 KB Output is correct
11 Correct 193 ms 25244 KB Output is correct
12 Correct 171 ms 25516 KB Output is correct
13 Correct 177 ms 24932 KB Output is correct
14 Incorrect 0 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -