oj.uz

Submission #893489

# Submission time Handle Problem Language Result Execution time Memory
893489 2023-12-27T05:48:44 Z vjudge1 Road Construction (JOI21_road_construction) C++17
38 / 100
 7378 ms 661644 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(){
	
 	
	
    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";
		}	
	} else{
		int cnt1 = 0;
	 	for(int i = 0;i < 1e18;i++){
	 		cnt1++;
		}
	}								
}

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 1078 ms 88732 KB Output is correct
2 Correct 1074 ms 88732 KB Output is correct
3 Correct 592 ms 53864 KB Output is correct
4 Correct 512 ms 53928 KB Output is correct
5 Correct 770 ms 74092 KB Output is correct
6 Correct 12 ms 2564 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3575 ms 389472 KB Output is correct
2 Correct 3399 ms 389792 KB Output is correct
3 Correct 384 ms 53844 KB Output is correct
4 Correct 3062 ms 419784 KB Output is correct
5 Correct 2379 ms 378372 KB Output is correct
6 Correct 2372 ms 378300 KB Output is correct
7 Correct 2478 ms 381396 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 155 ms 5056 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 1078 ms 88732 KB Output is correct
2 Correct 1074 ms 88732 KB Output is correct
3 Correct 592 ms 53864 KB Output is correct
4 Correct 512 ms 53928 KB Output is correct
5 Correct 770 ms 74092 KB Output is correct
6 Correct 12 ms 2564 KB Output is correct
7 Correct 5925 ms 563676 KB Output is correct
8 Correct 5667 ms 566492 KB Output is correct
9 Correct 463 ms 54004 KB Output is correct
10 Correct 5390 ms 494664 KB Output is correct
11 Correct 7378 ms 661644 KB Output is correct
12 Correct 3376 ms 488416 KB Output is correct
13 Correct 3748 ms 445448 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1078 ms 88732 KB Output is correct
2 Correct 1074 ms 88732 KB Output is correct
3 Correct 592 ms 53864 KB Output is correct
4 Correct 512 ms 53928 KB Output is correct
5 Correct 770 ms 74092 KB Output is correct
6 Correct 12 ms 2564 KB Output is correct
7 Correct 3575 ms 389472 KB Output is correct
8 Correct 3399 ms 389792 KB Output is correct
9 Correct 384 ms 53844 KB Output is correct
10 Correct 3062 ms 419784 KB Output is correct
11 Correct 2379 ms 378372 KB Output is correct
12 Correct 2372 ms 378300 KB Output is correct
13 Correct 2478 ms 381396 KB Output is correct
14 Incorrect 155 ms 5056 KB Output isn't correct
15 Halted 0 ms 0 KB -