oj.uz

Submission #893493

# Submission time Handle Problem Language Result Execution time Memory
893493 2023-12-27T05:51:35 Z abushbandit_1 Road Construction (JOI21_road_construction) C++17
38 / 100
 7753 ms 661512 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 925 ms 88912 KB Output is correct
2 Correct 931 ms 88568 KB Output is correct
3 Correct 502 ms 53744 KB Output is correct
4 Correct 458 ms 53928 KB Output is correct
5 Correct 725 ms 74092 KB Output is correct
6 Correct 11 ms 2652 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3370 ms 389640 KB Output is correct
2 Correct 3386 ms 389792 KB Output is correct
3 Correct 371 ms 53708 KB Output is correct
4 Correct 2955 ms 420272 KB Output is correct
5 Correct 2355 ms 378268 KB Output is correct
6 Correct 2357 ms 378252 KB Output is correct
7 Correct 2502 ms 381172 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 147 ms 4716 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 925 ms 88912 KB Output is correct
2 Correct 931 ms 88568 KB Output is correct
3 Correct 502 ms 53744 KB Output is correct
4 Correct 458 ms 53928 KB Output is correct
5 Correct 725 ms 74092 KB Output is correct
6 Correct 11 ms 2652 KB Output is correct
7 Correct 5652 ms 563720 KB Output is correct
8 Correct 5626 ms 566236 KB Output is correct
9 Correct 453 ms 53844 KB Output is correct
10 Correct 5542 ms 494580 KB Output is correct
11 Correct 7753 ms 661512 KB Output is correct
12 Correct 3366 ms 488300 KB Output is correct
13 Correct 3637 ms 445468 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 925 ms 88912 KB Output is correct
2 Correct 931 ms 88568 KB Output is correct
3 Correct 502 ms 53744 KB Output is correct
4 Correct 458 ms 53928 KB Output is correct
5 Correct 725 ms 74092 KB Output is correct
6 Correct 11 ms 2652 KB Output is correct
7 Correct 3370 ms 389640 KB Output is correct
8 Correct 3386 ms 389792 KB Output is correct
9 Correct 371 ms 53708 KB Output is correct
10 Correct 2955 ms 420272 KB Output is correct
11 Correct 2355 ms 378268 KB Output is correct
12 Correct 2357 ms 378252 KB Output is correct
13 Correct 2502 ms 381172 KB Output is correct
14 Incorrect 147 ms 4716 KB Output isn't correct
15 Halted 0 ms 0 KB -