oj.uz

답안 #893819

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
893819 2023-12-27T13:52:15 Z vjudge1 Road Construction (JOI21_road_construction) C++14
100 / 100
 9014 ms 573228 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;
multiset<int> ans;
const int N = 3e5;
struct pt {
	int x, y, id;
};
map<pii, bool> mp;
pt a[N];
int n, k;
bool cmp_x (const pt & a, const pt & b) {
	return a.x < b.x || (a.x == b.x && a.y < b.y);
}
 
bool cmp_y (const pt & a, const pt & b) {
	return a.y < b.y;
}
double mindist;
int ansa, ansb;
 
void upd_ans (const pt & a, const pt & b) {
	if(mp[{a.id,b.id}])return;
	mp[{a.id, b.id}] = 1;
	mp[{b.id, a.id}] = 1;
	int dist = abs(a.x-b.x) + abs(a.y-b.y);
	ans.insert(dist);
	while((int)ans.size()>k)ans.erase(prev(ans.end()));
	if((int)ans.size()>=k)mindist = *ans.rbegin();
}
void rec (int l, int r) {
	if (r - l <= 3) {
		for (int i=l; i<=r; ++i)
			for (int j=i+1; j<=r; ++j)
				upd_ans (a[i], a[j]);
		sort (a+l, a+r+1, &cmp_y);
		return;
	}
 
	int m = (l + r) >> 1;
	int midx = a[m].x;
	rec (l, m),  rec (m+1, r);
	static pt t[N];
	merge (a+l, a+m+1, a+m+1, a+r+1, t, &cmp_y);
	copy (t, t+r-l+1, a+l);
 
	int tsz = 0;
	for (int i=l; i<=r; ++i)
		if (abs (a[i].x - midx) < mindist) {
			for (int j=tsz-1; j>=0 && a[i].y - t[j].y < mindist; --j)
				upd_ans (a[i], t[j]);
			t[tsz++] = a[i];
		}
}
void solve(){
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i].x >> a[i].y;
		a[i].id = i;
	}
	sort (a, a+n, &cmp_x);
	mindist = 1e18;
	rec (0, n-1);
	for(auto i:ans){
		cout << 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:82:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   82 | main(){
      | ^~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1063 ms 75916 KB Output is correct
2 Correct 1042 ms 75956 KB Output is correct
3 Correct 540 ms 47952 KB Output is correct
4 Correct 548 ms 48304 KB Output is correct
5 Correct 855 ms 64088 KB Output is correct
6 Correct 10 ms 4184 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4769 ms 320304 KB Output is correct
2 Correct 4585 ms 320472 KB Output is correct
3 Correct 410 ms 47956 KB Output is correct
4 Correct 4191 ms 344376 KB Output is correct
5 Correct 3436 ms 311008 KB Output is correct
6 Correct 3413 ms 311376 KB Output is correct
7 Correct 3564 ms 313080 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 462 ms 57944 KB Output is correct
2 Correct 473 ms 58272 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 429 ms 57964 KB Output is correct
5 Correct 450 ms 58032 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 462 ms 57944 KB Output is correct
2 Correct 473 ms 58272 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 429 ms 57964 KB Output is correct
5 Correct 450 ms 58032 KB Output is correct
6 Correct 490 ms 57884 KB Output is correct
7 Correct 489 ms 57968 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 512 ms 57964 KB Output is correct
11 Correct 455 ms 58076 KB Output is correct
12 Correct 469 ms 58044 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1063 ms 75916 KB Output is correct
2 Correct 1042 ms 75956 KB Output is correct
3 Correct 540 ms 47952 KB Output is correct
4 Correct 548 ms 48304 KB Output is correct
5 Correct 855 ms 64088 KB Output is correct
6 Correct 10 ms 4184 KB Output is correct
7 Correct 6720 ms 460852 KB Output is correct
8 Correct 6662 ms 462648 KB Output is correct
9 Correct 450 ms 48040 KB Output is correct
10 Correct 5965 ms 404884 KB Output is correct
11 Correct 8260 ms 537988 KB Output is correct
12 Correct 4359 ms 400796 KB Output is correct
13 Correct 4567 ms 364312 KB Output is correct

Subtask #6
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1063 ms 75916 KB Output is correct
2 Correct 1042 ms 75956 KB Output is correct
3 Correct 540 ms 47952 KB Output is correct
4 Correct 548 ms 48304 KB Output is correct
5 Correct 855 ms 64088 KB Output is correct
6 Correct 10 ms 4184 KB Output is correct
7 Correct 4769 ms 320304 KB Output is correct
8 Correct 4585 ms 320472 KB Output is correct
9 Correct 410 ms 47956 KB Output is correct
10 Correct 4191 ms 344376 KB Output is correct
11 Correct 3436 ms 311008 KB Output is correct
12 Correct 3413 ms 311376 KB Output is correct
13 Correct 3564 ms 313080 KB Output is correct
14 Correct 462 ms 57944 KB Output is correct
15 Correct 473 ms 58272 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 429 ms 57964 KB Output is correct
18 Correct 450 ms 58032 KB Output is correct
19 Correct 490 ms 57884 KB Output is correct
20 Correct 489 ms 57968 KB Output is correct
21 Correct 1 ms 2392 KB Output is correct
22 Correct 0 ms 2396 KB Output is correct
23 Correct 512 ms 57964 KB Output is correct
24 Correct 455 ms 58076 KB Output is correct
25 Correct 469 ms 58044 KB Output is correct
26 Correct 6720 ms 460852 KB Output is correct
27 Correct 6662 ms 462648 KB Output is correct
28 Correct 450 ms 48040 KB Output is correct
29 Correct 5965 ms 404884 KB Output is correct
30 Correct 8260 ms 537988 KB Output is correct
31 Correct 4359 ms 400796 KB Output is correct
32 Correct 4567 ms 364312 KB Output is correct
33 Correct 8825 ms 572956 KB Output is correct
34 Correct 9014 ms 573228 KB Output is correct
35 Correct 8803 ms 567872 KB Output is correct
36 Correct 5633 ms 484904 KB Output is correct
37 Correct 5561 ms 485164 KB Output is correct
38 Correct 6002 ms 445024 KB Output is correct