oj.uz

Submission #682217

# Submission time Handle Problem Language Result Execution time Memory
682217 2023-01-16T04:39:50 Z vjudge1 Road Construction (JOI21_road_construction) C++17
32 / 100
 6030 ms 1066912 KB 
#include<bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

#define int long long
#define ll long long
#define pb push_back
#define ppb pop_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define freopen(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);

const int N = 250000 + 5;
const int M = 1e3 + 5;
const ll mod = 1e9 + 7;
const ll inf = 1e17;

int n, k, x[N], y[N], id[N], cc;
vector<pair<int, int>> ans;
vector<pair<pair<int, int>, int>> v;

int dist(int i, int j){
    return abs(x[i] - x[j]) + abs(y[i] - y[j]);
}

int convert(int i, int j){
    if(i < j) swap(i, j);
    return i * (n + 1) + j;
}

void solve(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i];
        x[i] += 1e9 + 5;
        y[i] += 1e9 + 5;
        v.pb({{x[i], y[i]}, i});
    }
    sort(all(v));
    cc = 20000000 / n;
    for(int i = 1; i <= n; i++){
        x[i] = v[i - 1].F.F;
        y[i] = v[i - 1].F.S;
        id[i] = v[i - 1].S;
        for(int j = max(1ll, j - cc); j < i; j++){
            ans.pb({dist(i, j), convert(id[i], id[j])});
        }
    }
    v.clear();
    for(int i = 1; i <= n; i++){
        v.pb({{x[i], y[i]}, id[i]});
    }
    sort(all(v));
    for(int i = 1; i <= n; i++){
        x[i] = v[i - 1].F.S;
        y[i] = v[i - 1].F.F;
        id[i] = v[i - 1].S;
        for(int j = max(1ll, j - cc); j < i; j++){
            ans.pb({dist(i, j), convert(id[i], id[j])});    
        }
    }
    sort(all(ans));
    for(int i = 0; i < ans.size(); i++){
        if(i + 1 < ans.size() && ans[i].S == ans[i + 1].S){
            continue;
        }
        cout << ans[i].F << '\n';
        k--;
        if(k == 0) break;
    }
    //N * log() * const
}

main() {
    fast
    int tt = 1;
    // cin >> tt;
    while(tt--){
        solve();
    }
}

Compilation message

road_construction.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization("O3")
      | 
road_construction.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization("unroll-loops")
      | 
road_construction.cpp:5: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    5 | #pragma comment(linker, "/stack:200000000")
      | 
road_construction.cpp: In function 'void solve()':
road_construction.cpp:70:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i = 0; i < ans.size(); i++){
      |                    ~~^~~~~~~~~~~~
road_construction.cpp:71:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         if(i + 1 < ans.size() && ans[i].S == ans[i + 1].S){
      |            ~~~~~~^~~~~~~~~~~~
road_construction.cpp: At global scope:
road_construction.cpp:81:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   81 | main() {
      | ^~~~
road_construction.cpp: In function 'void solve()':
road_construction.cpp:65:32: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |         for(int j = max(1ll, j - cc); j < i; j++){
      |                              ~~^~~~
road_construction.cpp:52:32: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |         for(int j = max(1ll, j - cc); j < i; j++){
      |                              ~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 18412 KB Output is correct
2 Correct 124 ms 18392 KB Output is correct
3 Correct 71 ms 10748 KB Output is correct
4 Correct 69 ms 10860 KB Output is correct
5 Correct 133 ms 17284 KB Output is correct
6 Correct 121 ms 16884 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5222 ms 1066820 KB Output is correct
2 Correct 5283 ms 1066912 KB Output is correct
3 Correct 61 ms 10708 KB Output is correct
4 Incorrect 5401 ms 1066720 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5214 ms 1066888 KB Output is correct
2 Correct 5085 ms 1066732 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 5322 ms 1066724 KB Output is correct
5 Correct 5296 ms 1066820 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5214 ms 1066888 KB Output is correct
2 Correct 5085 ms 1066732 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 5322 ms 1066724 KB Output is correct
5 Correct 5296 ms 1066820 KB Output is correct
6 Correct 5104 ms 1066904 KB Output is correct
7 Correct 5036 ms 1066728 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 6030 ms 1066712 KB Output is correct
11 Correct 5338 ms 1066824 KB Output is correct
12 Correct 5592 ms 1066884 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 18412 KB Output is correct
2 Correct 124 ms 18392 KB Output is correct
3 Correct 71 ms 10748 KB Output is correct
4 Correct 69 ms 10860 KB Output is correct
5 Correct 133 ms 17284 KB Output is correct
6 Correct 121 ms 16884 KB Output is correct
7 Incorrect 5270 ms 1057640 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 18412 KB Output is correct
2 Correct 124 ms 18392 KB Output is correct
3 Correct 71 ms 10748 KB Output is correct
4 Correct 69 ms 10860 KB Output is correct
5 Correct 133 ms 17284 KB Output is correct
6 Correct 121 ms 16884 KB Output is correct
7 Correct 5222 ms 1066820 KB Output is correct
8 Correct 5283 ms 1066912 KB Output is correct
9 Correct 61 ms 10708 KB Output is correct
10 Incorrect 5401 ms 1066720 KB Output isn't correct
11 Halted 0 ms 0 KB -