oj.uz

답안 #893501

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
893501 2023-12-27T05:55:31 Z vjudge1 Road Construction (JOI21_road_construction) C++17
45 / 100
 7444 ms 661544 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 || k == 1){
	    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

# 결과 실행 시간 메모리 Grader output
1 Correct 933 ms 88680 KB Output is correct
2 Correct 908 ms 88916 KB Output is correct
3 Correct 489 ms 53844 KB Output is correct
4 Correct 433 ms 54100 KB Output is correct
5 Correct 674 ms 74008 KB Output is correct
6 Correct 11 ms 2648 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3338 ms 389544 KB Output is correct
2 Correct 3299 ms 389920 KB Output is correct
3 Correct 367 ms 53524 KB Output is correct
4 Correct 2919 ms 419724 KB Output is correct
5 Correct 2325 ms 378436 KB Output is correct
6 Correct 2380 ms 378320 KB Output is correct
7 Correct 2410 ms 381228 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 339 ms 65884 KB Output is correct
2 Correct 334 ms 65972 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 262 ms 65976 KB Output is correct
5 Correct 344 ms 65876 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 339 ms 65884 KB Output is correct
2 Correct 334 ms 65972 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 262 ms 65976 KB Output is correct
5 Correct 344 ms 65876 KB Output is correct
6 Incorrect 150 ms 6592 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 933 ms 88680 KB Output is correct
2 Correct 908 ms 88916 KB Output is correct
3 Correct 489 ms 53844 KB Output is correct
4 Correct 433 ms 54100 KB Output is correct
5 Correct 674 ms 74008 KB Output is correct
6 Correct 11 ms 2648 KB Output is correct
7 Correct 5531 ms 563608 KB Output is correct
8 Correct 6088 ms 566084 KB Output is correct
9 Correct 510 ms 53824 KB Output is correct
10 Correct 5921 ms 494584 KB Output is correct
11 Correct 7444 ms 661544 KB Output is correct
12 Correct 3356 ms 488392 KB Output is correct
13 Correct 3576 ms 445600 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 933 ms 88680 KB Output is correct
2 Correct 908 ms 88916 KB Output is correct
3 Correct 489 ms 53844 KB Output is correct
4 Correct 433 ms 54100 KB Output is correct
5 Correct 674 ms 74008 KB Output is correct
6 Correct 11 ms 2648 KB Output is correct
7 Correct 3338 ms 389544 KB Output is correct
8 Correct 3299 ms 389920 KB Output is correct
9 Correct 367 ms 53524 KB Output is correct
10 Correct 2919 ms 419724 KB Output is correct
11 Correct 2325 ms 378436 KB Output is correct
12 Correct 2380 ms 378320 KB Output is correct
13 Correct 2410 ms 381228 KB Output is correct
14 Correct 339 ms 65884 KB Output is correct
15 Correct 334 ms 65972 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 262 ms 65976 KB Output is correct
18 Correct 344 ms 65876 KB Output is correct
19 Incorrect 150 ms 6592 KB Output isn't correct
20 Halted 0 ms 0 KB -