Submission #893493

#TimeUsernameProblemLanguageResultExecution timeMemory
893493abushbandit_1Road Construction (JOI21_road_construction)C++17
38 / 100
7753 ms661512 KiB
/* author : abushbandit platform : vjudge date : 27.12.2023 contest : Izho PREP (contest #8) problem : A - Road Construction for subtask 1,2,3 !!! */ #include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define all(x) x.begin(),x.end() #define ff first #define ss second const long long INF = 1e18; const int N = 1e5 + 1; vector<pair<int, int>> a; multiset<int> ans; map<pair<pair<int,int>,pair<int,int>>,bool> vis; int mn = INF; int n,k; int dist(pair<int, int> f, pair<int, int> s){ return abs(f.ff - s.ff) + abs(f.ss - s.ss); } void update(pair<int, int> f, pair<int, int> s){ if(vis[{f,s}] || vis[{s,f}]) return; ans.insert(dist(f, s)); vis[{f,s}] = 1; if(ans.size() == k) mn = *(-- ans.end()); else if(ans.size() > k) { ans.erase((--ans.end())); mn = *(--ans.end()); } } bool cmp(pair<int, int> f, pair<int, int> s){ return f.ss < s.ss; } void rec(int l, int r){ if (r - l <= 3) { for (int i = l; i < r; i++) { for (int j = i + 1; j <= r; j++) { update(a[i], a[j]); } } sort(a.begin() + l, a.begin() + r + 1, cmp); return; } int m = (l + r) >> 1; int md = a[m].ff; rec(l, m), rec(m + 1, r); vector<pair<int, int>> t(r - l + 1); merge(a.begin() + l, a.begin() + m + 1, a.begin() + m + 1, a.begin() + r + 1, t.begin(), cmp); copy(t.begin(), t.begin() + r - l + 1, a.begin() + l); int sz = 0; for (int i = l; i <= r; i++) { if (abs(a[i].ff - md) < mn) { for (int j = sz - 1; j >= 0 && a[i].ss - t[j].ss < mn; j--) { update(a[i], t[j]); } t[sz] = a[i]; sz++; } } } signed main(){ cin >> n >> k; int cnt = 0; for (int i = 0; i < n; i++) { int x, y; cin >> x >> y; if(y == 0){ cnt++; } a.pb({x, y}); } if(cnt == n || n <= 100000){ sort(all(a)); rec(0, n - 1); for(auto i : ans){ cout << i << "\n"; } } else{ int cnt1 = 0; for(int i = 0;i < 1e18;i++){ cnt1++; } } }

Compilation message (stderr)

road_construction.cpp: In function 'void update(std::pair<long long int, long long int>, std::pair<long long int, long long int>)':
road_construction.cpp:45:19: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   45 |     if(ans.size() == k) mn = *(-- ans.end());
      |        ~~~~~~~~~~~^~~~
road_construction.cpp:46:24: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   46 |     else if(ans.size() > k) {
      |             ~~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...