oj.uz

답안 #893558

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
893558 2023-12-27T07:01:12 Z vjudge1 Road Construction (JOI21_road_construction) C++17
27 / 100
 1815 ms 33260 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}) != st.end()){
		//cout << "was\n";
		return;
	}
	if((int)st.size() < k || (--st.end()) ->ff > dist){
		if((int)st.size() < k){
			st.insert({dist, a.id * b.id});
		}else{
			st.erase(--st.end());
			st.insert({dist, 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 = inf * 10;
	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:77:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   77 | main(){
      | ^~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 335 ms 20536 KB Output is correct
2 Correct 314 ms 20564 KB Output is correct
3 Correct 200 ms 20784 KB Output is correct
4 Correct 189 ms 20844 KB Output is correct
5 Incorrect 285 ms 19536 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1652 ms 30108 KB Output is correct
2 Correct 1753 ms 33132 KB Output is correct
3 Correct 161 ms 20576 KB Output is correct
4 Correct 1815 ms 33260 KB Output is correct
5 Incorrect 1568 ms 33108 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 13136 KB Output is correct
2 Correct 101 ms 13188 KB Output is correct
3 Correct 0 ms 2392 KB Output is correct
4 Correct 67 ms 13176 KB Output is correct
5 Correct 91 ms 13172 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 13136 KB Output is correct
2 Correct 101 ms 13188 KB Output is correct
3 Correct 0 ms 2392 KB Output is correct
4 Correct 67 ms 13176 KB Output is correct
5 Correct 91 ms 13172 KB Output is correct
6 Correct 104 ms 13172 KB Output is correct
7 Correct 107 ms 13172 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 104 ms 13180 KB Output is correct
11 Correct 70 ms 13140 KB Output is correct
12 Correct 89 ms 13140 KB Output is correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 335 ms 20536 KB Output is correct
2 Correct 314 ms 20564 KB Output is correct
3 Correct 200 ms 20784 KB Output is correct
4 Correct 189 ms 20844 KB Output is correct
5 Incorrect 285 ms 19536 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 335 ms 20536 KB Output is correct
2 Correct 314 ms 20564 KB Output is correct
3 Correct 200 ms 20784 KB Output is correct
4 Correct 189 ms 20844 KB Output is correct
5 Incorrect 285 ms 19536 KB Output isn't correct
6 Halted 0 ms 0 KB -