oj.uz

Submission #893475

# Submission time Handle Problem Language Result Execution time Memory
893475 2023-12-27T05:39:09 Z vjudge1 Road Construction (JOI21_road_construction) C++17
18 / 100
 3398 ms 420028 KB 
/*

author : abushbandit

platform : vjudge

date : 27.12.2023

contest : Izho PREP (contest #8)

problem : A - Road Construction

for subtask 1,2,3 !!!

*/


#include <bits/stdc++.h>

using namespace std;

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

const long long INF = 1e18;
const int N = 1e5 + 1;
 
vector<pair<int, int>> a;
multiset<int> ans;
map<pair<pair<int,int>,pair<int,int>>,bool> vis;
int mn = INF;
int n,k;
 
int dist(pair<int, int> f, pair<int, int> s){
    return abs(f.ff - s.ff) + abs(f.ss - s.ss);
}
 
void update(pair<int, int> f, pair<int, int> s){
	if(vis[{f,s}] || vis[{s,f}]) return;
    ans.insert(dist(f, s));
    vis[{f,s}] = 1;
    if(ans.size() == k) mn = *(--	ans.end());
    else if(ans.size() > k) {
        ans.erase((--ans.end()));
        mn = *(--ans.end());
    }
}
 
bool cmp(pair<int, int> f, pair<int, int> s){
    return f.ss < s.ss;
}
 
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++) {
                update(a[i], a[j]);
            }
        }
        sort(a.begin() + l, a.begin() + r + 1, cmp);
        return;
    }
 
    int m = (l + r) >> 1;
    int md = a[m].ff;
    rec(l, m), rec(m + 1, r);
    vector<pair<int, int>> t(r - l + 1);
    merge(a.begin() + l, a.begin() + m + 1, a.begin() + m + 1, a.begin() + r + 1, t.begin(), cmp);
    copy(t.begin(), t.begin() + r - l + 1, a.begin() + l);
 
    int sz = 0;
    for (int i = l; i <= r; i++) {
        if (abs(a[i].ff - md) < mn) {
            for (int j = sz - 1; j >= 0 && a[i].ss - t[j].ss < mn; j--) {
                update(a[i], t[j]);
            }
            t[sz] = a[i];
            sz++;
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 	
    cin >> n >> k;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        if(y == 0){
        	cnt++;
		}
        a.pb({x, y});
    }
    if(cnt == n || k <= 9 || n <= 1000){
	    sort(all(a));
	    rec(0, n - 1);
	    for(auto i : ans){
	    	cout << i << "\n";
		}	
	}									
}

Compilation message

road_construction.cpp: In function 'void update(std::pair<long long int, long long int>, std::pair<long long int, long long int>)':
road_construction.cpp:45:19: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   45 |     if(ans.size() == k) mn = *(-- ans.end());
      |        ~~~~~~~~~~~^~~~
road_construction.cpp:46:24: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   46 |     else if(ans.size() > k) {
      |             ~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1020 ms 88700 KB Output is correct
2 Correct 966 ms 88664 KB Output is correct
3 Correct 508 ms 53944 KB Output is correct
4 Correct 449 ms 53808 KB Output is correct
5 Correct 708 ms 74068 KB Output is correct
6 Correct 10 ms 2652 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3398 ms 389788 KB Output is correct
2 Correct 3269 ms 389752 KB Output is correct
3 Correct 371 ms 53692 KB Output is correct
4 Correct 2981 ms 420028 KB Output is correct
5 Correct 2328 ms 378592 KB Output is correct
6 Correct 2340 ms 378316 KB Output is correct
7 Correct 2551 ms 381404 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 66060 KB Output is correct
2 Correct 233 ms 65980 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 200 ms 65964 KB Output is correct
5 Correct 253 ms 66276 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 66060 KB Output is correct
2 Correct 233 ms 65980 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 200 ms 65964 KB Output is correct
5 Correct 253 ms 66276 KB Output is correct
6 Incorrect 41 ms 5076 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1020 ms 88700 KB Output is correct
2 Correct 966 ms 88664 KB Output is correct
3 Correct 508 ms 53944 KB Output is correct
4 Correct 449 ms 53808 KB Output is correct
5 Correct 708 ms 74068 KB Output is correct
6 Correct 10 ms 2652 KB Output is correct
7 Incorrect 17 ms 2472 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1020 ms 88700 KB Output is correct
2 Correct 966 ms 88664 KB Output is correct
3 Correct 508 ms 53944 KB Output is correct
4 Correct 449 ms 53808 KB Output is correct
5 Correct 708 ms 74068 KB Output is correct
6 Correct 10 ms 2652 KB Output is correct
7 Correct 3398 ms 389788 KB Output is correct
8 Correct 3269 ms 389752 KB Output is correct
9 Correct 371 ms 53692 KB Output is correct
10 Correct 2981 ms 420028 KB Output is correct
11 Correct 2328 ms 378592 KB Output is correct
12 Correct 2340 ms 378316 KB Output is correct
13 Correct 2551 ms 381404 KB Output is correct
14 Correct 230 ms 66060 KB Output is correct
15 Correct 233 ms 65980 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 200 ms 65964 KB Output is correct
18 Correct 253 ms 66276 KB Output is correct
19 Incorrect 41 ms 5076 KB Output isn't correct
20 Halted 0 ms 0 KB -