oj.uz

Submission #618541

# Submission time Handle Problem Language Result Execution time Memory
618541 2022-08-02T05:24:27 Z joelau Road Construction (JOI21_road_construction) C++14
18 / 100
 658 ms 59356 KB 
#include <bits/stdc++.h>
using namespace std;

long long N,K;
pair<long long,long long> lst[250005];
vector<long long> A;
priority_queue< tuple<long long,long long,long long>, vector< tuple<long long,long long,long long> >, greater< tuple<long long,long long,long long> > > pq;
set< pair<long long,long long> > s;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> N >> K;
	for (long long i = 0; i < N; ++i) cin >> lst[i].first >> lst[i].second;
	if (N <= 1000) {
		for (long long i = 0; i < N; ++i) for (long long j = i+1; j < N; ++j)
			A.push_back(abs(lst[i].first-lst[j].first)+abs(lst[i].second-lst[j].second));
		sort(A.begin(),A.end());
		for (long long i = 0; i < K; ++i) cout << A[i] << '\n';
	}
	else {
		sort(lst,lst+N);
		for (long long i = 0; i < N-1; ++i) {
			pq.emplace(abs(lst[i+1].first-lst[i].first)+abs(lst[i+1].second-lst[i].second),i,i+1);
			s.emplace(i,i+1);
		}
		long long cnt = 0;
		while (!pq.empty() && cnt < K) {
			long long d,a,b; tie(d,a,b) = pq.top(); pq.pop();
			cout << d << '\n';
			cnt++;
			if (a != 0 && s.find(make_pair(a-1,b)) == s.end()) {
				pq.emplace(abs(lst[b].first-lst[a-1].first)+abs(lst[b].second-lst[a-1].second),a-1,b);
				s.emplace(a-1,b);
			}
			if (b != N-1 && s.find(make_pair(a,b+1)) == s.end()) {
				pq.emplace(abs(lst[b+1].first-lst[a].first)+abs(lst[b+1].second-lst[a].second),a,b+1);
				s.emplace(a,b+1);
			}
		}
	}
	
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 6968 KB Output is correct
2 Correct 59 ms 6988 KB Output is correct
3 Correct 37 ms 5072 KB Output is correct
4 Correct 37 ms 5100 KB Output is correct
5 Correct 54 ms 5824 KB Output is correct
6 Correct 19 ms 4624 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 655 ms 54932 KB Output is correct
2 Correct 658 ms 54936 KB Output is correct
3 Correct 42 ms 4928 KB Output is correct
4 Correct 381 ms 45448 KB Output is correct
5 Correct 259 ms 45524 KB Output is correct
6 Correct 272 ms 45680 KB Output is correct
7 Correct 335 ms 59356 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 30856 KB Output is correct
2 Correct 141 ms 30828 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 117 ms 28568 KB Output is correct
5 Correct 137 ms 31084 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 30856 KB Output is correct
2 Correct 141 ms 30828 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 117 ms 28568 KB Output is correct
5 Correct 137 ms 31084 KB Output is correct
6 Incorrect 139 ms 30808 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 6968 KB Output is correct
2 Correct 59 ms 6988 KB Output is correct
3 Correct 37 ms 5072 KB Output is correct
4 Correct 37 ms 5100 KB Output is correct
5 Correct 54 ms 5824 KB Output is correct
6 Correct 19 ms 4624 KB Output is correct
7 Incorrect 422 ms 41256 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 6968 KB Output is correct
2 Correct 59 ms 6988 KB Output is correct
3 Correct 37 ms 5072 KB Output is correct
4 Correct 37 ms 5100 KB Output is correct
5 Correct 54 ms 5824 KB Output is correct
6 Correct 19 ms 4624 KB Output is correct
7 Correct 655 ms 54932 KB Output is correct
8 Correct 658 ms 54936 KB Output is correct
9 Correct 42 ms 4928 KB Output is correct
10 Correct 381 ms 45448 KB Output is correct
11 Correct 259 ms 45524 KB Output is correct
12 Correct 272 ms 45680 KB Output is correct
13 Correct 335 ms 59356 KB Output is correct
14 Correct 143 ms 30856 KB Output is correct
15 Correct 141 ms 30828 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 117 ms 28568 KB Output is correct
18 Correct 137 ms 31084 KB Output is correct
19 Incorrect 139 ms 30808 KB Output isn't correct
20 Halted 0 ms 0 KB -