Submission #640803

#	Time	Username	Problem	Language	Result	Execution time	Memory
640803		Son	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	89 ms	6724 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second

int K,N;
char Ax[10], Bx[10];
int A[100005], B[100005];
vector < int > V;
LL lsum = 0, rsum = 0;
LL P[100005], S[100005];
priority_queue < int > lpq;
priority_queue < int , vector < int > , greater < int > > rpq;

bool cmp( int a, int b ){
    return A[a] + B[a] < A[b] + B[b];
}

void reset(){
    lsum = rsum = 0;
    while ( !lpq.empty() ) lpq.pop();
    while ( !rpq.empty() ) rpq.pop();
}

void add( int x ){
    if ( lpq.empty() || x <= lpq.top() ){
        lpq.push(x);
        lsum += x;
    } else {
        rpq.push(x);
        rsum += x;
    }

    if ( rpq.size() + 1 < lpq.size() ){
        int y = lpq.top();
        lpq.pop();
        rpq.push(y);
        lsum -= y;
        rsum += y;
    } else if ( lpq.size() < rpq.size() ){
        int y = rpq.top();
        rpq.pop();
        lpq.push(y);
        rsum -= y;
        lsum += y;
    }
}

int main(){

    LL ss = 0, bridges = 0;
    scanf("%d%d",&K,&N);
    for ( int i = 1; i <= N; i++ ){
        scanf("%s%d%s%d",&Ax,&A[i],&Bx,&B[i]);
        if ( A[i] > B[i] ){
            swap(A[i],B[i]);
        }
        if ( Ax[0] == Bx[0] ){
            ss += B[i] - A[i];
        } else {
            bridges += 1;
            V.push_back(i);
        }
    }
    sort(V.begin(),V.end(),cmp);
    
    reset();
    for ( int i = 0; i < V.size(); i++ ){
        int id = V[i];
        add(A[id]);
        add(B[id]);
        P[i] = rsum - lsum;
    }
    
    reset();
    for ( int i = V.size()-1; i >= 0; i-- ){
        int id = V[i];
        add(A[id]);
        add(B[id]);
        S[i] = rsum - lsum;
    }

    LL ans = P[V.size()-1] + ss + bridges;
    for ( int i = 0; i < V.size() && K == 2; i++ ){
        LL temp = ss + bridges + S[i];
        if ( i ) temp += P[i-1];
        if ( temp < ans ) ans = temp;
    }

    printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:57:17: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[10]' [-Wformat=]
   57 |         scanf("%s%d%s%d",&Ax,&A[i],&Bx,&B[i]);
      |                ~^        ~~~
      |                 |        |
      |                 char*    char (*)[10]
bridge.cpp:57:21: warning: format '%s' expects argument of type 'char*', but argument 4 has type 'char (*)[10]' [-Wformat=]
   57 |         scanf("%s%d%s%d",&Ax,&A[i],&Bx,&B[i]);
      |                    ~^              ~~~
      |                     |              |
      |                     char*          char (*)[10]
bridge.cpp:71:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for ( int i = 0; i < V.size(); i++ ){
      |                      ~~^~~~~~~~~~
bridge.cpp:87:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for ( int i = 0; i < V.size() && K == 2; i++ ){
      |                      ~~^~~~~~~~~~
bridge.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d%d",&K,&N);
      |     ~~~~~^~~~~~~~~~~~~~
bridge.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%s%d%s%d",&Ax,&A[i],&Bx,&B[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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