oj.uz

Submission #893818

# Submission time Handle Problem Language Result Execution time Memory
893818 2023-12-27T13:50:21 Z Nurislam Road Construction (JOI21_road_construction) C++14
100 / 100
 8923 ms 573472 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

# Verdict Execution time Memory Grader output
1 Correct 920 ms 76008 KB Output is correct
2 Correct 934 ms 75696 KB Output is correct
3 Correct 504 ms 48100 KB Output is correct
4 Correct 467 ms 47960 KB Output is correct
5 Correct 757 ms 64080 KB Output is correct
6 Correct 10 ms 4188 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4577 ms 320216 KB Output is correct
2 Correct 4524 ms 321024 KB Output is correct
3 Correct 399 ms 47928 KB Output is correct
4 Correct 4121 ms 344292 KB Output is correct
5 Correct 3383 ms 311216 KB Output is correct
6 Correct 3426 ms 311520 KB Output is correct
7 Correct 3558 ms 313276 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 57940 KB Output is correct
2 Correct 462 ms 57960 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 453 ms 58192 KB Output is correct
5 Correct 442 ms 57916 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 57940 KB Output is correct
2 Correct 462 ms 57960 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 453 ms 58192 KB Output is correct
5 Correct 442 ms 57916 KB Output is correct
6 Correct 516 ms 57888 KB Output is correct
7 Correct 481 ms 58204 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 476 ms 58036 KB Output is correct
11 Correct 443 ms 58184 KB Output is correct
12 Correct 478 ms 58192 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 920 ms 76008 KB Output is correct
2 Correct 934 ms 75696 KB Output is correct
3 Correct 504 ms 48100 KB Output is correct
4 Correct 467 ms 47960 KB Output is correct
5 Correct 757 ms 64080 KB Output is correct
6 Correct 10 ms 4188 KB Output is correct
7 Correct 6642 ms 460472 KB Output is correct
8 Correct 6547 ms 462660 KB Output is correct
9 Correct 448 ms 48212 KB Output is correct
10 Correct 6020 ms 404416 KB Output is correct
11 Correct 8178 ms 537940 KB Output is correct
12 Correct 4346 ms 400016 KB Output is correct
13 Correct 4491 ms 364456 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 920 ms 76008 KB Output is correct
2 Correct 934 ms 75696 KB Output is correct
3 Correct 504 ms 48100 KB Output is correct
4 Correct 467 ms 47960 KB Output is correct
5 Correct 757 ms 64080 KB Output is correct
6 Correct 10 ms 4188 KB Output is correct
7 Correct 4577 ms 320216 KB Output is correct
8 Correct 4524 ms 321024 KB Output is correct
9 Correct 399 ms 47928 KB Output is correct
10 Correct 4121 ms 344292 KB Output is correct
11 Correct 3383 ms 311216 KB Output is correct
12 Correct 3426 ms 311520 KB Output is correct
13 Correct 3558 ms 313276 KB Output is correct
14 Correct 453 ms 57940 KB Output is correct
15 Correct 462 ms 57960 KB Output is correct
16 Correct 1 ms 2392 KB Output is correct
17 Correct 453 ms 58192 KB Output is correct
18 Correct 442 ms 57916 KB Output is correct
19 Correct 516 ms 57888 KB Output is correct
20 Correct 481 ms 58204 KB Output is correct
21 Correct 0 ms 2396 KB Output is correct
22 Correct 0 ms 2396 KB Output is correct
23 Correct 476 ms 58036 KB Output is correct
24 Correct 443 ms 58184 KB Output is correct
25 Correct 478 ms 58192 KB Output is correct
26 Correct 6642 ms 460472 KB Output is correct
27 Correct 6547 ms 462660 KB Output is correct
28 Correct 448 ms 48212 KB Output is correct
29 Correct 6020 ms 404416 KB Output is correct
30 Correct 8178 ms 537940 KB Output is correct
31 Correct 4346 ms 400016 KB Output is correct
32 Correct 4491 ms 364456 KB Output is correct
33 Correct 8923 ms 572548 KB Output is correct
34 Correct 8798 ms 573472 KB Output is correct
35 Correct 8672 ms 568028 KB Output is correct
36 Correct 5618 ms 485080 KB Output is correct
37 Correct 5678 ms 485192 KB Output is correct
38 Correct 6476 ms 444932 KB Output is correct