oj.uz

Submission #893484

# Submission time Handle Problem Language Result Execution time Memory
893484 2023-12-27T05:45:43 Z vjudge1 Road Construction (JOI21_road_construction) C++17
38 / 100
 7790 ms 661820 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(){
	
 	int cnt1 = 0;
 	for(int i = 0;i < 1e8;i++){
 		cnt1++;
	}
	
    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 || 	n <= 100000){
	    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 917 ms 88616 KB Output is correct
2 Correct 902 ms 88788 KB Output is correct
3 Correct 479 ms 53904 KB Output is correct
4 Correct 457 ms 53800 KB Output is correct
5 Correct 713 ms 74260 KB Output is correct
6 Correct 11 ms 2648 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3370 ms 389580 KB Output is correct
2 Correct 3361 ms 389880 KB Output is correct
3 Correct 365 ms 53772 KB Output is correct
4 Correct 3044 ms 419892 KB Output is correct
5 Correct 2377 ms 378300 KB Output is correct
6 Correct 2381 ms 378488 KB Output is correct
7 Correct 2539 ms 381508 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 153 ms 4636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 153 ms 4636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 917 ms 88616 KB Output is correct
2 Correct 902 ms 88788 KB Output is correct
3 Correct 479 ms 53904 KB Output is correct
4 Correct 457 ms 53800 KB Output is correct
5 Correct 713 ms 74260 KB Output is correct
6 Correct 11 ms 2648 KB Output is correct
7 Correct 6003 ms 563748 KB Output is correct
8 Correct 5853 ms 566108 KB Output is correct
9 Correct 480 ms 53804 KB Output is correct
10 Correct 5645 ms 494544 KB Output is correct
11 Correct 7790 ms 661820 KB Output is correct
12 Correct 3371 ms 488264 KB Output is correct
13 Correct 3605 ms 445516 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 917 ms 88616 KB Output is correct
2 Correct 902 ms 88788 KB Output is correct
3 Correct 479 ms 53904 KB Output is correct
4 Correct 457 ms 53800 KB Output is correct
5 Correct 713 ms 74260 KB Output is correct
6 Correct 11 ms 2648 KB Output is correct
7 Correct 3370 ms 389580 KB Output is correct
8 Correct 3361 ms 389880 KB Output is correct
9 Correct 365 ms 53772 KB Output is correct
10 Correct 3044 ms 419892 KB Output is correct
11 Correct 2377 ms 378300 KB Output is correct
12 Correct 2381 ms 378488 KB Output is correct
13 Correct 2539 ms 381508 KB Output is correct
14 Incorrect 153 ms 4636 KB Output isn't correct
15 Halted 0 ms 0 KB -