oj.uz

Submission #682219

# Submission time Handle Problem Language Result Execution time Memory
682219 2023-01-16T04:41:33 Z vjudge1 Road Construction (JOI21_road_construction) C++17
32 / 100
 8814 ms 1066924 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 = 30000000 / 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 18596 KB Output is correct
2 Correct 137 ms 18624 KB Output is correct
3 Correct 73 ms 10864 KB Output is correct
4 Correct 70 ms 10944 KB Output is correct
5 Correct 139 ms 17432 KB Output is correct
6 Correct 120 ms 16948 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7919 ms 1066816 KB Output is correct
2 Correct 8401 ms 1066924 KB Output is correct
3 Correct 64 ms 10716 KB Output is correct
4 Incorrect 8037 ms 1066836 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 7620 ms 1066856 KB Output is correct
2 Correct 7665 ms 1066708 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 8625 ms 1066752 KB Output is correct
5 Correct 8342 ms 1066764 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7620 ms 1066856 KB Output is correct
2 Correct 7665 ms 1066708 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 8625 ms 1066752 KB Output is correct
5 Correct 8342 ms 1066764 KB Output is correct
6 Correct 7600 ms 1066772 KB Output is correct
7 Correct 7700 ms 1066808 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 8814 ms 1066860 KB Output is correct
11 Correct 7952 ms 1066704 KB Output is correct
12 Correct 7854 ms 1066828 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 18596 KB Output is correct
2 Correct 137 ms 18624 KB Output is correct
3 Correct 73 ms 10864 KB Output is correct
4 Correct 70 ms 10944 KB Output is correct
5 Correct 139 ms 17432 KB Output is correct
6 Correct 120 ms 16948 KB Output is correct
7 Incorrect 7586 ms 1057624 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 18596 KB Output is correct
2 Correct 137 ms 18624 KB Output is correct
3 Correct 73 ms 10864 KB Output is correct
4 Correct 70 ms 10944 KB Output is correct
5 Correct 139 ms 17432 KB Output is correct
6 Correct 120 ms 16948 KB Output is correct
7 Correct 7919 ms 1066816 KB Output is correct
8 Correct 8401 ms 1066924 KB Output is correct
9 Correct 64 ms 10716 KB Output is correct
10 Incorrect 8037 ms 1066836 KB Output isn't correct
11 Halted 0 ms 0 KB -