Submission #893821

#	Time	Username	Problem	Language	Result	Execution time	Memory
893821		Minbaev	Road Construction (JOI21_road_construction)	C++17	33 / 100	2371 ms	218684 KiB

road_construction

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long
#define pii pair<int,int>
 
using i64 = long long;
 
template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}
 
template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}
 
 
const int N = 1e5 * 4 + 1;
 
vector<int>g[N];
const int inf = 1e16;
 
int n;
 
struct SegTree{
    ar <int,2> T[N * 4];
    SegTree(){
        for ( int i = 0; i < N * 4; i++ ){
            T[i] = {inf, -1};
        }
    }
    void upd(int v, int l, int r, int pos, int val, int id){
        if ( l == r ){
            T[v] = {val, id};
            return;
        }
        int md = (l + r) >> 1;
        if ( pos > md ){
            upd(v * 2 + 1, md + 1, r, pos, val, id);
        } else{
            upd(v * 2, l, md, pos, val, id);
        }
        T[v] = min(T[v * 2], T[v * 2 + 1]);
    };
    void upd(int pos, int val, int id){
        upd(1, 0, n - 1, pos, val, id);
    }
    auto get(int v, int l, int r, int tl, int tr){
        if ( l > tr or r < tl ){
            return ar<int,2>{inf, -1};
        }
        if ( tl <= l && tr >= r ){
            return T[v];
        }
        int md = (l + r) >> 1;
        return min(get(v * 2, l, md, tl, tr), get(v * 2 + 1, md + 1, r, tl, tr));
    }
    auto get(int l, int r){
        return get(1, 0, n - 1, l, r);
    }
} s1, s2;
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
	int k;
    cin >> n >> k;
    vector<vector<int>>vsg(n+1,{0,0});
    vector <ar<int,3>> a(n);
    int ind = 0;
    vector <int> pos;
    for ( auto &[x, y, i]: a ){
        cin >> x >> y;
        vsg[ind][0] = x;
        vsg[ind][1] = y;
        i = ind++;
        pos.pb(y);
        
    }
    sort(all(a)), sort(all(pos));
    pos.resize(unique(all(pos)) - pos.begin());
    auto get = [&](int u){
        return lower_bound(all(pos), u) - pos.begin();
    };
    vector <int> opt(n, inf), ans(n);
    {
        for ( auto &[x, y, i]: a ){
            int q = get(y);
            auto [v1, j1] = s1.get(0, q);
            v1 += x + y;
            auto [v2, j2] = s2.get(q, n - 1);
            v2 += x - y;
            if ( v1 > v2 ){
                swap(v1, v2), swap(j1, j2);
            }
            opt[i] = v1, ans[i] = j1;
            
            
             if(0<=j1&&j1<n)
				g[i].pb(j1);
            if(0<=j2&&j2<n)
				g[i].pb(j2);
            
            s1.upd(q, -y - x, i);
            s2.upd(q, -x + y, i);
        }
    }
    for ( int i = 0; i < n; i++ ){
        s1.upd(i, inf, -1);
        s2.upd(i, inf, -1);
    }
    {
        reverse(all(a));
        for ( auto &[x, y, i]: a ){
            int q = get(y);
            auto [v1, j1] = s1.get(0, q);
            v1 += -x + y;
            auto [v2, j2] = s2.get(q, n - 1);
            v2 += -x - y;
            if ( v1 > v2 ){
                swap(v1, v2), swap(j1, j2);
            }
            if(0<=j1&&j1<n)
				g[i].pb(j1);
            if(0<=j2&&j2<n)
				g[i].pb(j2);
            
            if ( chmin(opt[i], v1) ){
                ans[i] = j1;
            }
            s1.upd(q, x - y, i);
            s2.upd(q, x + y, i);
        }
    }
   
    vector<int>u;
    priority_queue <pair<int,pii>, vector <pair<int,pii>>, greater <pair<int,pii>> > q;
    map<pii,int>mp;
    
    for(int i = 0; i<n;i++){
		mp[{i,i}] = 1;
		for(auto to:g[i]){
			if(mp[{i,to}]==1)continue;
			q.push({abs(vsg[i][0] - vsg[to][0]) + abs(vsg[i][1]-vsg[to][1]),{i,to}});
			mp[{i,to}] = 1;
			mp[{to,i}] = 1;
			//~ cout<<i<<" "<<to<<"\n";
		}	
		
	}
	
    while(u.size()<k){
		auto [cost,x] = q.top();
		q.pop();
		//~ cout<<x.first<<"-"<<x.second<<endl;
		u.pb(cost);
		
		for(auto to:g[x.first]){
			if(mp[{x.second,to}]==1)continue;
			q.push({abs(vsg[x.second][0] - vsg[to][0]) + abs(vsg[x.second][1]-vsg[to][1]),{x.second,to}});
			mp[{x.second,to}] = 1;
			mp[{to,x.second}] = 1;
		}
		
		for(auto to:g[x.second]){
			if(mp[{x.first,to}]==1)continue;
			q.push({abs(vsg[x.first][0] - vsg[to][0]) + abs(vsg[x.first][1]-vsg[to][1]),{x.first,to}});
			mp[{x.first,to}] = 1;
			mp[{to,x.first}] = 1;
		}
	
	}
    
	for(auto to:u)cout<<to<<"\n";
 
   
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:167:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  167 |     while(u.size()<k){
      |           ~~~~~~~~^~

• Subtask 1: 0 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35