oj.uz

Submission #893571

# Submission time Handle Problem Language Result Execution time Memory
893571 2023-12-27T07:08:40 Z vjudge1 Road Construction (JOI21_road_construction) C++17
27 / 100
 1809 ms 30364 KB 
#include <bits/stdc++.h>

#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long

using namespace std;

int pow(int a,int b,int m){int ans=1;while(b){if(b&1){ans=(ans*a)%m;}b>>=1;a=(a*a)%m;}return ans;}
int binpow(int a,int b){int ans=1;while(b){if(b&1){ans=(ans*a);}b>>=1;a=(a*a);}return ans;}
	
const int N = 1e5 + 2, inf = 1e9, MAXN = 3e5;
int k;
struct pt {
	int x, y, id;
};

inline bool cmp_x (const pt & a, const pt & b) {
	return a.x < b.x || a.x == b.x && a.y < b.y;
}
 
inline bool cmp_y (const pt & a, const pt & b) {
	return a.y < b.y;
}
 
pt a[MAXN];
int mindist;
int ansa, ansb;
multiset <pair <int,int>> st;

inline void upd_ans (const pt & a, const pt & b) {
	int dist = abs(a.x-b.x) + abs(a.y-b.y);
	if(st.find({dist, a.id * b.id + min(a.id, b.id)}) != st.end()){
		return;
	}
	if((int)st.size() < k || (--st.end()) ->ff > dist){
		if((int)st.size() < k){
			st.insert({dist, a.id * b.id+ min(a.id, b.id)});
		}else{
			st.erase(--st.end());
			st.insert({dist, a.id * b.id+ min(a.id, b.id)});
		}
	}
	if((int)st.size() == k)
		mindist = (--st.end()) ->ff;
}

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[MAXN];
	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];
		}
}

main(){
	iostream::sync_with_stdio(false);	
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
		cin >> a[i].x >> a[i].y;
		a[i].id = i + 1;
	}
    sort (a, a+n, &cmp_x);
    mindist = 1e18;
	rec (0, n-1);
	for(auto x : st){
		cout << x.ff <<"\n";
	}
	
	
}

Compilation message

road_construction.cpp: In function 'bool cmp_x(const pt&, const pt&)':
road_construction.cpp:22:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   22 |  return a.x < b.x || a.x == b.x && a.y < b.y;
      |                      ~~~~~~~~~~~^~~~~~~~~~~~
road_construction.cpp: At global scope:
road_construction.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   76 | main(){
      | ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 20848 KB Output is correct
2 Correct 395 ms 20720 KB Output is correct
3 Correct 216 ms 20820 KB Output is correct
4 Correct 181 ms 20612 KB Output is correct
5 Incorrect 281 ms 19644 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1702 ms 30364 KB Output is correct
2 Correct 1635 ms 30012 KB Output is correct
3 Correct 149 ms 20560 KB Output is correct
4 Correct 1809 ms 29852 KB Output is correct
5 Incorrect 1651 ms 30108 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 13140 KB Output is correct
2 Correct 101 ms 13172 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 68 ms 13172 KB Output is correct
5 Correct 87 ms 13140 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 13140 KB Output is correct
2 Correct 101 ms 13172 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 68 ms 13172 KB Output is correct
5 Correct 87 ms 13140 KB Output is correct
6 Correct 102 ms 13172 KB Output is correct
7 Correct 102 ms 13172 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 108 ms 13176 KB Output is correct
11 Correct 68 ms 13140 KB Output is correct
12 Correct 95 ms 13396 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 20848 KB Output is correct
2 Correct 395 ms 20720 KB Output is correct
3 Correct 216 ms 20820 KB Output is correct
4 Correct 181 ms 20612 KB Output is correct
5 Incorrect 281 ms 19644 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 20848 KB Output is correct
2 Correct 395 ms 20720 KB Output is correct
3 Correct 216 ms 20820 KB Output is correct
4 Correct 181 ms 20612 KB Output is correct
5 Incorrect 281 ms 19644 KB Output isn't correct
6 Halted 0 ms 0 KB -