Submission #946018

#	Time	Username	Problem	Language	Result	Execution time	Memory
946018		hmm789	Road Construction (JOI21_road_construction)	C++14	0 / 100	10052 ms	43020 KiB

road_construction

#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 (stderr)

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
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35