제출 #490588

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
490588		DeadlyCritic	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	14 ms	19532 KiB

bridge

#include <bits/stdc++.h>
// #pragma GCC optimize ("O2,unroll-loops")
// #pragma GCC optimize("no-stack-protector,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define IOS ios::sync_with_stdio(0), cin.tie(), cout.tie();

#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define uni(v) sort(all(v)), v.erase(unique(all(v)), v.end())

// #define c0 (v << 1)
// #define c1 (c0 | 1)
// #define md ((l+r)>>1)

using namespace std;

typedef long long ll;

const int maxN = 2e5+7;


int k, n, sz;
ll fix;

vector<pair<int, int>> ed;

vector<int> df;

map<int, int> mp;
int demp[maxN];

pair<int, int> pr[maxN];
vector<int> st[maxN], en[maxN];


ll dis(pair<int, int> a, ll p){
    return abs(a.fr-p)+abs(a.sc-p)+1;
}

int sumer(pair<int, int> a){
    return a.fr+a.sc;
}

int sumer(int a, int b){
    return a+b;
}

signed main(){IOS


    cin >> k >> n;
    

    for(int i = 0; i < n; i++){
        char t1, t2;
        int x1, x2;
        cin >> t1 >> x1 >> t2 >> x2;
        if(t1 == t2){
            fix += abs(x2-x1);
        }
        else{
            ed.push_back({min(x1, x2), max(x1, x2)});
            df.push_back(x1);
            df.push_back(x2);
        }
    }

    assert(k == 2);

    n = ed.size();

    uni(df);

    sz = df.size();

    if(sz == 1){
        cout << 0 << '\n';
        return 0;
    }

    for(int i = 0; i < sz; i++)mp[df[i]] = i, demp[i] = df[i];

    for(int i = 0; i < n; i++){
        ed[i].fr = mp[ed[i].fr];
        ed[i].sc = mp[ed[i].sc];
        pr[i] = {ed[i].fr, ed[i].sc};
        st[ed[i].fr].push_back(i);
        en[ed[i].sc].push_back(i);
    }
    
    if(k == 1){
        int po = 0;
        ll now = 0;
        int l = en[po].size(), r = n-st[po].size();

        for(int i = 0; i < n; i++){
            ll x = dis({demp[ed[i].fr], demp[ed[i].sc]}, demp[po]);
            now += x;
        }

        ll ans = now;

        while(po+1 < sz){
            ll delt = demp[po+1]-demp[po];
            now += (l*2-r*2)*delt;
            ans = min(ans, now);
            po++;
            l += en[po].size();
            r -= st[po].size();
        }

        cout << fix+ans << '\n';
        return 0;
    }
    
    ll ans = 1e15;

    for(int i = 1; i < sz; i++){
        priority_queue<pair<int, int>> pq;

        ll nw = 0;
        for(int j = 0; j < ed.size(); j++){
            if(ed[j].sc < i)pq.push({-sumer(ed[j]), j});
            nw += dis({demp[ed[j].fr], demp[ed[j].sc]}, demp[i]);
        }

        for(int j = 0; j < i; j++){
            while(pq.size() && -pq.top().fr < i+j){
                nw -= dis({demp[pr[pq.top().sc].fr], demp[pr[pq.top().sc].sc]}, demp[i]);
                nw += dis({demp[pr[pq.top().sc].fr], demp[pr[pq.top().sc].sc]}, demp[j]);
                pq.pop();
            }
            ans = min(ans, nw);
        }
    }

    cout << fix+ans << '\n';

}

/*

1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

===

24

===

2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

===

22

===

2 10
A 1 B 1
A 5 B 5
A 5 B 5
A 5 B 5
A 5 B 5
A 5 B 5
A 5 B 5
A 5 B 5
A 6 B 10
A 6 B 10

===

18

===

*/

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'int main()':
bridge.cpp:124:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         for(int j = 0; j < ed.size(); j++){
      |                        ~~^~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37