oj.uz

Submission #893561

# Submission time Handle Problem Language Result Execution time Memory
893561 2023-12-27T07:04:33 Z vjudge1 Road Construction (JOI21_road_construction) C++17
27 / 100
 1907 ms 30360 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()){
		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 * n;
	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 333 ms 20728 KB Output is correct
2 Correct 314 ms 20560 KB Output is correct
3 Correct 192 ms 20560 KB Output is correct
4 Correct 211 ms 20816 KB Output is correct
5 Incorrect 259 ms 19540 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1562 ms 30104 KB Output is correct
2 Correct 1636 ms 30360 KB Output is correct
3 Correct 147 ms 20632 KB Output is correct
4 Correct 1766 ms 30100 KB Output is correct
5 Incorrect 1907 ms 30112 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 107 ms 13172 KB Output is correct
2 Correct 118 ms 13184 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 70 ms 13360 KB Output is correct
5 Correct 93 ms 13172 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 13172 KB Output is correct
2 Correct 118 ms 13184 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 70 ms 13360 KB Output is correct
5 Correct 93 ms 13172 KB Output is correct
6 Correct 121 ms 13168 KB Output is correct
7 Correct 129 ms 13188 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 121 ms 13172 KB Output is correct
11 Correct 73 ms 13176 KB Output is correct
12 Correct 97 ms 13140 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 20728 KB Output is correct
2 Correct 314 ms 20560 KB Output is correct
3 Correct 192 ms 20560 KB Output is correct
4 Correct 211 ms 20816 KB Output is correct
5 Incorrect 259 ms 19540 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 20728 KB Output is correct
2 Correct 314 ms 20560 KB Output is correct
3 Correct 192 ms 20560 KB Output is correct
4 Correct 211 ms 20816 KB Output is correct
5 Incorrect 259 ms 19540 KB Output isn't correct
6 Halted 0 ms 0 KB -