oj.uz

Submission #682324

# Submission time Handle Problem Language Result Execution time Memory
682324 2023-01-16T06:22:38 Z vjudge1 Road Construction (JOI21_road_construction) C++17
38 / 100
 8439 ms 1066884 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 = 2; 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 125 ms 18588 KB Output is correct
2 Correct 132 ms 18588 KB Output is correct
3 Correct 81 ms 10832 KB Output is correct
4 Correct 83 ms 10960 KB Output is correct
5 Correct 131 ms 17436 KB Output is correct
6 Correct 125 ms 16976 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 26972 KB Output is correct
2 Correct 511 ms 28452 KB Output is correct
3 Correct 62 ms 2892 KB Output is correct
4 Correct 238 ms 28240 KB Output is correct
5 Correct 251 ms 28380 KB Output is correct
6 Correct 262 ms 28492 KB Output is correct
7 Correct 262 ms 27900 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7988 ms 1066796 KB Output is correct
2 Correct 7941 ms 1066700 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 134 ms 25672 KB Output is correct
5 Correct 8379 ms 1066884 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7988 ms 1066796 KB Output is correct
2 Correct 7941 ms 1066700 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 134 ms 25672 KB Output is correct
5 Correct 8379 ms 1066884 KB Output is correct
6 Correct 7939 ms 1066748 KB Output is correct
7 Correct 7620 ms 1066800 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 8439 ms 1066724 KB Output is correct
11 Correct 118 ms 25864 KB Output is correct
12 Correct 7990 ms 1066788 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 18588 KB Output is correct
2 Correct 132 ms 18588 KB Output is correct
3 Correct 81 ms 10832 KB Output is correct
4 Correct 83 ms 10960 KB Output is correct
5 Correct 131 ms 17436 KB Output is correct
6 Correct 125 ms 16976 KB Output is correct
7 Incorrect 7436 ms 1057708 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 18588 KB Output is correct
2 Correct 132 ms 18588 KB Output is correct
3 Correct 81 ms 10832 KB Output is correct
4 Correct 83 ms 10960 KB Output is correct
5 Correct 131 ms 17436 KB Output is correct
6 Correct 125 ms 16976 KB Output is correct
7 Correct 481 ms 26972 KB Output is correct
8 Correct 511 ms 28452 KB Output is correct
9 Correct 62 ms 2892 KB Output is correct
10 Correct 238 ms 28240 KB Output is correct
11 Correct 251 ms 28380 KB Output is correct
12 Correct 262 ms 28492 KB Output is correct
13 Correct 262 ms 27900 KB Output is correct
14 Correct 7988 ms 1066796 KB Output is correct
15 Correct 7941 ms 1066700 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 134 ms 25672 KB Output is correct
18 Correct 8379 ms 1066884 KB Output is correct
19 Correct 7939 ms 1066748 KB Output is correct
20 Correct 7620 ms 1066800 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 8439 ms 1066724 KB Output is correct
24 Correct 118 ms 25864 KB Output is correct
25 Correct 7990 ms 1066788 KB Output is correct
26 Incorrect 7436 ms 1057708 KB Output isn't correct
27 Halted 0 ms 0 KB -