Submission #107134

#	Time	Username	Problem	Language	Result	Execution time	Memory
107134		oolimry	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	3 ms	384 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

typedef pair<long long, long long> ii;
int main()
{
    //freopen("i.txt","r",stdin);
    int k, n;

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> k >> n;

    vector<ii> points;
    vector<ii> pairs;
    long long forcedDist = 0ll;

    for(int i = 0;i < n;i++){
        char a, c;
        long long b, d;
        cin >> a >> b >> c >> d;

        if(a == c){
            forcedDist += abs(d-b);
        }
        else{
            forcedDist += abs(d-b);
            forcedDist++;
            if(b > d) swap(b,d);
            points.push_back(ii(b,i));
            points.push_back(ii(d,i));
            pairs.push_back(ii(b,d));
        }
    }

    n = points.size();
    sort(points.begin(),points.end());
    for(int i = 0;i < n;i++){
        //cout << points[i].first << " " << points[i].second << "\n";
    }

    long long a = 0;
    long long b = 0;
    long long minVal = 102345678901234567;
    for(b = 0;b < n;b++){
        long long x = points[a].first;
        long long y = points[b].first;
        long long val = 0ll;
        for(int j = 0;j < pairs.size();j++){
            long long p = pairs[j].first;
            long long q = pairs[j].second;
            if((x <= q)&&(p <= x) || (y <= q)&&(p <= y)) continue;
            val += min(min(abs(p-x),abs(p-y)),min(abs(q-x),abs(q-y)));
        }
        minVal = min(minVal,val);
        //cout << x << " " << y << " " << val << "\n";
        while(a < b){
            long long x = points[a].first;
            long long y = points[b].first;
            long long val2 = 0ll;
            for(int j = 0;j < pairs.size();j++){
                long long p = pairs[j].first;
                long long q = pairs[j].second;
                if((x <= q)&&(p <= x) || (y <= q)&&(p <= y)) continue;
                val2 += min(min(abs(p-x),abs(p-y)),min(abs(q-x),abs(q-y)));
            }
            if(val2 <= val){
                val = val2;
                //cout << x << " " << y << " " << val << " f\n";
                minVal = min(minVal,val);
                a++; ///upgrade
            }
            else{
                break;
            }
        }
        a--; ///go back
    }

    cout << 2ll * minVal + forcedDist;





    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:51:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < pairs.size();j++){
                       ~~^~~~~~~~~~~~~~
bridge.cpp:54:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
             if((x <= q)&&(p <= x) || (y <= q)&&(p <= y)) continue;
                ~~~~~~~~^~~~~~~~~~
bridge.cpp:63:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0;j < pairs.size();j++){
                           ~~^~~~~~~~~~~~~~
bridge.cpp:66:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                 if((x <= q)&&(p <= x) || (y <= q)&&(p <= y)) continue;
                    ~~~~~~~~^~~~~~~~~~

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