oj.uz

Submission #893467

# Submission time Handle Problem Language Result Execution time Memory
893467 2023-12-27T05:31:36 Z vjudge1 Road Construction (JOI21_road_construction) C++17
18 / 100
 3484 ms 419752 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 == 1 || 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 1014 ms 88716 KB Output is correct
2 Correct 978 ms 88628 KB Output is correct
3 Correct 526 ms 53840 KB Output is correct
4 Correct 501 ms 53876 KB Output is correct
5 Correct 718 ms 74108 KB Output is correct
6 Correct 10 ms 2648 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3484 ms 389868 KB Output is correct
2 Correct 3433 ms 389812 KB Output is correct
3 Correct 374 ms 53584 KB Output is correct
4 Correct 3019 ms 419752 KB Output is correct
5 Correct 2335 ms 378228 KB Output is correct
6 Correct 2358 ms 378316 KB Output is correct
7 Correct 2450 ms 381372 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 65980 KB Output is correct
2 Correct 232 ms 65948 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 197 ms 65852 KB Output is correct
5 Correct 239 ms 66072 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 65980 KB Output is correct
2 Correct 232 ms 65948 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 197 ms 65852 KB Output is correct
5 Correct 239 ms 66072 KB Output is correct
6 Incorrect 41 ms 4820 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1014 ms 88716 KB Output is correct
2 Correct 978 ms 88628 KB Output is correct
3 Correct 526 ms 53840 KB Output is correct
4 Correct 501 ms 53876 KB Output is correct
5 Correct 718 ms 74108 KB Output is correct
6 Correct 10 ms 2648 KB Output is correct
7 Incorrect 17 ms 2516 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1014 ms 88716 KB Output is correct
2 Correct 978 ms 88628 KB Output is correct
3 Correct 526 ms 53840 KB Output is correct
4 Correct 501 ms 53876 KB Output is correct
5 Correct 718 ms 74108 KB Output is correct
6 Correct 10 ms 2648 KB Output is correct
7 Correct 3484 ms 389868 KB Output is correct
8 Correct 3433 ms 389812 KB Output is correct
9 Correct 374 ms 53584 KB Output is correct
10 Correct 3019 ms 419752 KB Output is correct
11 Correct 2335 ms 378228 KB Output is correct
12 Correct 2358 ms 378316 KB Output is correct
13 Correct 2450 ms 381372 KB Output is correct
14 Correct 235 ms 65980 KB Output is correct
15 Correct 232 ms 65948 KB Output is correct
16 Correct 0 ms 600 KB Output is correct
17 Correct 197 ms 65852 KB Output is correct
18 Correct 239 ms 66072 KB Output is correct
19 Incorrect 41 ms 4820 KB Output isn't correct
20 Halted 0 ms 0 KB -