Submission #487331

#	Time	Username	Problem	Language	Result	Execution time	Memory
487331		leaked	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	1 ms	328 KiB

bridge

#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define vec vector
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define fast_iati ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll inf=1e18;
signed main(){
    fast_iati;

    int id=-1;
    int k,n;
    cin>>k>>n;
    vec<int>l,r;
    ll ans=0;
    vec<int>kek;
    vec<int>pref;
    for(int i=0;i<n;i++){
        char f,s;
        int x,y;
        cin>>f>>x>>s>>y;
        if(f==s) ans+=abs(x-y);
        else{
            if(x>y) swap(x,y);
            l.pb(x);r.pb(y);
        }
    }
    n=sz(l);
    for(int i=0;i<n;i++){
        kek.pb(l[i]);kek.pb(r[i]);
    }
    sort(all(kek));kek.erase(unique(all(kek)),kek.end());
    pref.assign(sz(kek)+1,0);
    for(int i=0;i<n;i++){
        l[i]=lower_bound(all(kek),l[i])-kek.begin();
        r[i]=lower_bound(all(kek),r[i])-kek.begin();
        pref[l[i]]++,pref[r[i]+1]--;
        cout<<kek[l[i]]<<' '<<kek[r[i]]<<endl;
    }
    for(int i=1;i<=sz(kek);i++){
        pref[i]+=pref[i-1];
    }
    int j=*max_element(all(pref));
    if(k==1){
        ll mn=inf;
        for(int i=0;i<sz(kek);i++){
            int x=kek[i];
            if(pref[i]!=j) continue;
            ll me=0;
            for(int k=0;k<n;k++)
                me+=abs(x-kek[l[k]])+abs(x-kek[r[k]])+1;
//            cout<<"ALO "<<x<<' '<<me<<endl;
            umin(mn,me);
        }
//        cout<<ans<<endl;
        cout<<ans+mn;
    }
    else{
    cout<<22;}
    return 0;
}
/*
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:23:9: warning: unused variable 'id' [-Wunused-variable]
   23 |     int id=-1;
      |         ^~

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