oj.uz

Submission #682215

# Submission time Handle Problem Language Result Execution time Memory
682215 2023-01-16T04:38:44 Z vjudge1 Road Construction (JOI21_road_construction) C++17
32 / 100
 2491 ms 283828 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 = 10000000 / 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 121 ms 17356 KB Output is correct
2 Correct 122 ms 17384 KB Output is correct
3 Correct 67 ms 10236 KB Output is correct
4 Correct 69 ms 10364 KB Output is correct
5 Correct 129 ms 16912 KB Output is correct
6 Correct 110 ms 16976 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2293 ms 278768 KB Output is correct
2 Correct 2250 ms 281816 KB Output is correct
3 Correct 59 ms 10120 KB Output is correct
4 Incorrect 2309 ms 281864 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 2137 ms 278752 KB Output is correct
2 Correct 2206 ms 281528 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 2397 ms 281496 KB Output is correct
5 Correct 2388 ms 281520 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2137 ms 278752 KB Output is correct
2 Correct 2206 ms 281528 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 2397 ms 281496 KB Output is correct
5 Correct 2388 ms 281520 KB Output is correct
6 Correct 2370 ms 283828 KB Output is correct
7 Correct 2292 ms 282144 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2491 ms 282144 KB Output is correct
11 Correct 2469 ms 281740 KB Output is correct
12 Correct 2280 ms 282092 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 17356 KB Output is correct
2 Correct 122 ms 17384 KB Output is correct
3 Correct 67 ms 10236 KB Output is correct
4 Correct 69 ms 10364 KB Output is correct
5 Correct 129 ms 16912 KB Output is correct
6 Correct 110 ms 16976 KB Output is correct
7 Incorrect 2080 ms 269856 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 17356 KB Output is correct
2 Correct 122 ms 17384 KB Output is correct
3 Correct 67 ms 10236 KB Output is correct
4 Correct 69 ms 10364 KB Output is correct
5 Correct 129 ms 16912 KB Output is correct
6 Correct 110 ms 16976 KB Output is correct
7 Correct 2293 ms 278768 KB Output is correct
8 Correct 2250 ms 281816 KB Output is correct
9 Correct 59 ms 10120 KB Output is correct
10 Incorrect 2309 ms 281864 KB Output isn't correct
11 Halted 0 ms 0 KB -