oj.uz

Submission #946018

# Submission time Handle Problem Language Result Execution time Memory
946018 2024-03-14T09:38:58 Z hmm789 Road Construction (JOI21_road_construction) C++14
0 / 100
 10000 ms 43020 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define INF 1000000000000000000
#define MOD 1000000007

const int B = 730;

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, k;
	cin >> n >> k;
	int x[n], y[n];
	for(int i = 0; i < n; i++) cin >> x[i] >> y[i];
	pair<int, int> p[n];
	for(int i = 0; i < n; i++) p[i] = {x[i]+y[i], i};
	sort(p, p+n);
	priority_queue<tuple<int, int, int>> pq, pq2;
	for(int i = 0; i < n; i++) {
		for(int j = i+1; j < min(n, i+B); j++) {
			int i1 = p[i].second, i2 = p[j].second;
			if(i1 > i2) swap(i1, i2);
			if(abs(x[i1]-x[i2])+abs(y[i1]-y[i2]) > p[j].first-p[i].first) continue;
			if((int)pq.size() < k) pq.push({p[j].first-p[i].first, i1, i2});
			else {
				pq.pop();
				pq.push({p[j].first-p[i].first, i1, i2});
			}
		}
	}
	for(int i = 0; i < n; i++) p[i] = {x[i]-y[i], i};
	sort(p, p+n);
	for(int i = 0; i < n; i++) {
		for(int j = i+1; j < min(n, i+B); j++) {
			int i1 = p[i].second, i2 = p[j].second;
			if(i1 > i2) swap(i1, i2);
			if(abs(x[i1]-x[i2])+abs(y[i1]-y[i2]) > p[j].first-p[i].first) continue;
			if((int)pq2.size() < k) pq2.push({p[j].first-p[i].first, i1, i2});
			else {
				pq2.pop();
				pq2.push({p[j].first-p[i].first, i1, i2});
			}
		}
	}
	vector<tuple<int, int, int>> a1, a2;
	while(!pq.empty()) {
		a1.push_back(pq.top());
		pq.pop();
	}
	while(!pq2.empty()) {
		a2.push_back(pq2.top());
		pq2.pop();
	}
	set<pair<int, int>> v;
	vector<int> ans;
	reverse(a1.begin(), a1.end());
	reverse(a2.begin(), a2.end());
	/*for(auto [a,b,c] : a1) cout << a << " " << b << " " << c << endl;
	cout << "fff" << endl;
	for(auto [a,b,c] : a2) cout << a << " " << b << " " << c << endl;*/
	int i1 = 0, i2 = 0;
	while(i1 < a1.size() && i2 < a2.size()) {
		//cout << i1 << " " << i2 << " " << get<0>(a1[i1]) << " "<< get<0>(a2[i2]) << endl;
		if(get<0>(a1[i1]) < get<0>(a2[i2])) {
			int a, b, c;
			tie(a, b, c) = a1[i1];
			if(v.find({b,c}) != v.end()) {
				i1++;
				continue;
			}
			ans.push_back(a);
			v.insert({b, c});
			i1++;
		} else {
			int a, b, c;
			tie(a, b, c) = a2[i2];
			if(v.find({b,c}) != v.end()) {
				i2++;
				continue;
			}
			ans.push_back(a);
			v.insert({b, c});
			i2++;
		}
		if((int)ans.size() == k) break;
	}
	for(int i : ans) cout << i << '\n';
}

Compilation message

road_construction.cpp: In function 'int32_t main()':
road_construction.cpp:63:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int>, std::allocator<std::tuple<long long int, long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  while(i1 < a1.size() && i2 < a2.size()) {
      |        ~~~^~~~~~~~~~~
road_construction.cpp:63:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int>, std::allocator<std::tuple<long long int, long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  while(i1 < a1.size() && i2 < a2.size()) {
      |                          ~~~^~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 43020 KB Output is correct
2 Correct 235 ms 41904 KB Output is correct
3 Incorrect 252 ms 32248 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10052 ms 14964 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 43020 KB Output is correct
2 Correct 235 ms 41904 KB Output is correct
3 Incorrect 252 ms 32248 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 43020 KB Output is correct
2 Correct 235 ms 41904 KB Output is correct
3 Incorrect 252 ms 32248 KB Output isn't correct
4 Halted 0 ms 0 KB -