oj.uz

Submission #893581

# Submission time Handle Problem Language Result Execution time Memory
893581 2023-12-27T07:12:54 Z vjudge1 Road Construction (JOI21_road_construction) C++17
27 / 100
 1686 ms 30108 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;
}

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 309 ms 20564 KB Output is correct
2 Correct 321 ms 20572 KB Output is correct
3 Correct 193 ms 20564 KB Output is correct
4 Correct 180 ms 20640 KB Output is correct
5 Incorrect 261 ms 19404 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1546 ms 30096 KB Output is correct
2 Correct 1550 ms 30100 KB Output is correct
3 Correct 155 ms 20804 KB Output is correct
4 Correct 1686 ms 30108 KB Output is correct
5 Incorrect 1529 ms 30100 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 98 ms 13176 KB Output is correct
2 Correct 99 ms 13136 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 66 ms 13168 KB Output is correct
5 Correct 84 ms 13136 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 13176 KB Output is correct
2 Correct 99 ms 13136 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 66 ms 13168 KB Output is correct
5 Correct 84 ms 13136 KB Output is correct
6 Correct 101 ms 13140 KB Output is correct
7 Correct 103 ms 13108 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 102 ms 13172 KB Output is correct
11 Correct 67 ms 13140 KB Output is correct
12 Correct 86 ms 13136 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 20564 KB Output is correct
2 Correct 321 ms 20572 KB Output is correct
3 Correct 193 ms 20564 KB Output is correct
4 Correct 180 ms 20640 KB Output is correct
5 Incorrect 261 ms 19404 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 20564 KB Output is correct
2 Correct 321 ms 20572 KB Output is correct
3 Correct 193 ms 20564 KB Output is correct
4 Correct 180 ms 20640 KB Output is correct
5 Incorrect 261 ms 19404 KB Output isn't correct
6 Halted 0 ms 0 KB -