oj.uz

Submission #893605

# Submission time Handle Problem Language Result Execution time Memory
893605 2023-12-27T07:25:17 Z vjudge1 Road Construction (JOI21_road_construction) C++17
27 / 100
 1894 ms 30292 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#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 + 1;
}

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:24:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   24 |  return a.x < b.x || a.x == b.x && a.y < b.y;
      |                      ~~~~~~~~~~~^~~~~~~~~~~~
road_construction.cpp: At global scope:
road_construction.cpp:78:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   78 | main(){
      | ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 20648 KB Output is correct
2 Correct 333 ms 20564 KB Output is correct
3 Correct 204 ms 20816 KB Output is correct
4 Correct 199 ms 20816 KB Output is correct
5 Incorrect 279 ms 19560 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1678 ms 30108 KB Output is correct
2 Correct 1677 ms 30292 KB Output is correct
3 Correct 147 ms 20560 KB Output is correct
4 Correct 1894 ms 29848 KB Output is correct
5 Incorrect 1761 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 102 ms 13420 KB Output is correct
2 Correct 100 ms 13176 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 68 ms 13136 KB Output is correct
5 Correct 116 ms 13164 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 13420 KB Output is correct
2 Correct 100 ms 13176 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 68 ms 13136 KB Output is correct
5 Correct 116 ms 13164 KB Output is correct
6 Correct 124 ms 13172 KB Output is correct
7 Correct 101 ms 13172 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 102 ms 13164 KB Output is correct
11 Correct 71 ms 13172 KB Output is correct
12 Correct 162 ms 13172 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 20648 KB Output is correct
2 Correct 333 ms 20564 KB Output is correct
3 Correct 204 ms 20816 KB Output is correct
4 Correct 199 ms 20816 KB Output is correct
5 Incorrect 279 ms 19560 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 20648 KB Output is correct
2 Correct 333 ms 20564 KB Output is correct
3 Correct 204 ms 20816 KB Output is correct
4 Correct 199 ms 20816 KB Output is correct
5 Incorrect 279 ms 19560 KB Output isn't correct
6 Halted 0 ms 0 KB -