oj.uz

답안 #893871

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
893871 2023-12-27T15:24:03 Z Minbaev Road Construction (JOI21_road_construction) C++17
33 / 100
 2424 ms 312396 KB 
#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>
 
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 = 1e6;
 
vector<int>g[N];
const int inf = 1e17+7;
 
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;
		}	
		
	}
	
    while(u.size()<k){
		auto [cost,x] = q.top();
		q.pop();
		
		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

road_construction.cpp: In function 'int main()':
road_construction.cpp:164: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]
  164 |     while(u.size()<k){
      |           ~~~~~~~~^~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1263 ms 189532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2424 ms 290788 KB Output is correct
2 Correct 2395 ms 290788 KB Output is correct
3 Correct 671 ms 184920 KB Output is correct
4 Correct 1797 ms 273460 KB Output is correct
5 Correct 1715 ms 275036 KB Output is correct
6 Correct 1715 ms 275140 KB Output is correct
7 Correct 2241 ms 298536 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2123 ms 307500 KB Output is correct
2 Correct 2110 ms 312364 KB Output is correct
3 Correct 23 ms 149084 KB Output is correct
4 Correct 745 ms 242188 KB Output is correct
5 Correct 1304 ms 272880 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2123 ms 307500 KB Output is correct
2 Correct 2110 ms 312364 KB Output is correct
3 Correct 23 ms 149084 KB Output is correct
4 Correct 745 ms 242188 KB Output is correct
5 Correct 1304 ms 272880 KB Output is correct
6 Correct 2209 ms 312396 KB Output is correct
7 Correct 2227 ms 311572 KB Output is correct
8 Correct 23 ms 149084 KB Output is correct
9 Correct 24 ms 149084 KB Output is correct
10 Correct 2192 ms 312076 KB Output is correct
11 Correct 740 ms 242256 KB Output is correct
12 Correct 1223 ms 273788 KB Output is correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1263 ms 189532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1263 ms 189532 KB Output isn't correct
2 Halted 0 ms 0 KB -