oj.uz

Submission #682323

# Submission time Handle Problem Language Result Execution time Memory
682323 2023-01-16T06:21:59 Z vjudge1 Road Construction (JOI21_road_construction) C++17
32 / 100
 9196 ms 1069064 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;
}

set<pair<int, pair<int, int>>> st;
bool ok2 = 1;

void solve(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i];
        if(y[i] != 0) ok2 = 0;
        x[i] += 1e9 + 5;
        y[i] += 1e9 + 5;
        v.pb({{x[i], y[i]}, i});
    }
    sort(all(v));
    if(ok2){
        for(int i = 1; i <= n; i++){
            x[i] = v[i - 1].F.F;
            y[i] = v[i - 1].F.S;
        }
        for(int i = 1; i <= n; i++){
            st.insert({x[i] - x[i - 1], {i, i - 1}});
        }
        while(k--){
            auto to = *st.begin();
            cout << to.F << '\n';
            if(to.S.S != 1){
                st.insert({x[to.S.F] - x[to.S.S - 1], {to.S.F, to.S.S - 1}});
            }
            st.erase(to);
        }
        return;
    }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:91: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]
   91 |     for(int i = 0; i < ans.size(); i++){
      |                    ~~^~~~~~~~~~~~
road_construction.cpp:92: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]
   92 |         if(i + 1 < ans.size() && ans[i].S == ans[i + 1].S){
      |            ~~~~~~^~~~~~~~~~~~
road_construction.cpp: At global scope:
road_construction.cpp:102:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  102 | main() {
      | ^~~~
road_construction.cpp: In function 'void solve()':
road_construction.cpp:86:32: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |         for(int j = max(1ll, j - cc); j < i; j++){
      |                              ~~^~~~
road_construction.cpp:73:32: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |         for(int j = max(1ll, j - cc); j < i; j++){
      |                              ~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 18640 KB Output is correct
2 Correct 130 ms 18532 KB Output is correct
3 Correct 74 ms 10884 KB Output is correct
4 Correct 72 ms 10960 KB Output is correct
5 Correct 127 ms 17452 KB Output is correct
6 Correct 124 ms 16896 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8055 ms 1068940 KB Output is correct
2 Correct 7649 ms 1069032 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 127 ms 27996 KB Output is correct
5 Correct 7930 ms 1068956 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8055 ms 1068940 KB Output is correct
2 Correct 7649 ms 1069032 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 127 ms 27996 KB Output is correct
5 Correct 7930 ms 1068956 KB Output is correct
6 Correct 7536 ms 1068972 KB Output is correct
7 Correct 7834 ms 1069064 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 9196 ms 1068956 KB Output is correct
11 Correct 120 ms 27924 KB Output is correct
12 Correct 8282 ms 1068956 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 18640 KB Output is correct
2 Correct 130 ms 18532 KB Output is correct
3 Correct 74 ms 10884 KB Output is correct
4 Correct 72 ms 10960 KB Output is correct
5 Correct 127 ms 17452 KB Output is correct
6 Correct 124 ms 16896 KB Output is correct
7 Incorrect 7843 ms 1059644 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 18640 KB Output is correct
2 Correct 130 ms 18532 KB Output is correct
3 Correct 74 ms 10884 KB Output is correct
4 Correct 72 ms 10960 KB Output is correct
5 Correct 127 ms 17452 KB Output is correct
6 Correct 124 ms 16896 KB Output is correct
7 Incorrect 372 ms 30668 KB Output isn't correct
8 Halted 0 ms 0 KB -