oj.uz

Submission #297339

# Submission time Handle Problem Language Result Execution time Memory
297339 2020-09-11T13:56:50 Z AaronNaidu Palembang Bridges (APIO15_bridge) C++14
31 / 100
 2000 ms 4980 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll k, n;
ll s, t, numLeft, numRight, distFrom0;
char p, q;
vector<pair<ll, ll> > events;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> k >> n;
    ll minSum = 0;
    numLeft = numRight = distFrom0 = 0;
    if (k == 1)
    {
        for (int i = 0; i < n; i++)
        {
            cin >> p >> s >> q >> t;
            if (p == q)
            {
                minSum += abs(t - s);
            }
            else
            {
                minSum += 1 + abs(t - s);
                ll b = max(t, s);
                ll a = min(t, s);
                events.push_back({a, -1});
                events.push_back({b, 1});
                numRight++;
                distFrom0 += a;
            }
        }
        //cout << "Min sum is " << minSum << "\n";
        //cout << "Initial dist: " << distFrom0 << "\n";
        sort(events.begin(), events.end());
        ll prevLocation = 0;
        ll finAns = 1000000000000000;
        if (events.size() == 0)
        {
            finAns = minSum;
        }
        for (int i = 0; i < events.size(); i++)
        {
            ll currLocation = events[i].first;
            distFrom0 -= numRight * (currLocation - prevLocation);
            distFrom0 += numLeft * (currLocation - prevLocation);
            if (events[i].second == -1)
            {
                numRight--;
            }
            else
            {
                numLeft++;
            }
            finAns = min(finAns, minSum + 2 * distFrom0);
            //cout << "At location " << currLocation << " dist is " << distFrom0 << '\n'; 
            prevLocation = currLocation;
        }
        cout << finAns << "\n";
        return 0;
    }
    for (int i = 0; i < n; i++)
    {
        cin >> p >> s >> q >> t;
        if (p == q)
        {
            minSum += abs(t - s);
        }
        else
        {
            minSum += 1 + abs(t - s);
            ll b = max(t, s);
            ll a = min(t, s);
            events.push_back({a, b});
        }
    }
    if(events.size() < 2) {
        cout << minSum << "\n";
        return 0;
    }
    //sort(events.begin(), events.end());
    ll finAns = 1000000000000000;
    for (int i = 0; i < events.size(); i++)
    {
        for (int j = i+1; j < events.size(); j++)
        {
            ll bri1 = events[i].first;
            ll bri2 = events[j].first;
            ll bridge1 = min(bri1, bri2);
            ll bridge2 = max(bri1, bri2);
            ll totAddOn = 0;
            for (int k = 0; k < events.size(); k++)
            {
                if(events[k].second <= bridge1) {
                    totAddOn += 2 * (bridge1-events[k].second);
                }
                else if (events[k].first >= bridge2)
                {
                    totAddOn += 2 * (events[k].first-bridge2);
                }
                else if (events[k].first > bridge1 and events[k].second < bridge2)
                {
                    totAddOn += 2 * min(events[k].first-bridge1, bridge2-events[k].second);
                }
            }
            finAns = min(finAns, minSum + totAddOn);

            bri1 = events[i].second;
            bri2 = events[j].first;
            bridge1 = min(bri1, bri2);
            bridge2 = max(bri1, bri2);
            totAddOn = 0;
            for (int k = 0; k < events.size(); k++)
            {
                if(events[k].second <= bridge1) {
                    totAddOn += 2 * (bridge1-events[k].second);
                }
                else if (events[k].first >= bridge2)
                {
                    totAddOn += 2 * (events[k].first-bridge2);
                }
                else if (events[k].first > bridge1 and events[k].second < bridge2)
                {
                    totAddOn += 2 * min(events[k].first-bridge1, bridge2-events[k].second);
                }
            }
            finAns = min(finAns, minSum + totAddOn);
            
            bri1 = events[i].first;
            bri2 = events[j].second;
            bridge1 = min(bri1, bri2);
            bridge2 = max(bri1, bri2);
            totAddOn = 0;
            for (int k = 0; k < events.size(); k++)
            {
                if(events[k].second <= bridge1) {
                    totAddOn += 2 * (bridge1-events[k].second);
                }
                else if (events[k].first >= bridge2)
                {
                    totAddOn += 2 * (events[k].first-bridge2);
                }
                else if (events[k].first > bridge1 and events[k].second < bridge2)
                {
                    totAddOn += 2 * min(events[k].first-bridge1, bridge2-events[k].second);
                }
            }
            finAns = min(finAns, minSum + totAddOn);
            
            bri1 = events[i].second;
            bri2 = events[j].second;
            bridge1 = min(bri1, bri2);
            bridge2 = max(bri1, bri2);
            totAddOn = 0;
            for (int k = 0; k < events.size(); k++)
            {
                if(events[k].second <= bridge1) {
                    totAddOn += 2 * (bridge1-events[k].second);
                }
                else if (events[k].first >= bridge2)
                {
                    totAddOn += 2 * (events[k].first-bridge2);
                }
                else if (events[k].first > bridge1 and events[k].second < bridge2)
                {
                    totAddOn += 2 * min(events[k].first-bridge1, bridge2-events[k].second);
                }
            }
            finAns = min(finAns, minSum + totAddOn);
        }
    }
    cout << finAns << "\n";    
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:47:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (int i = 0; i < events.size(); i++)
      |                         ~~^~~~~~~~~~~~~~~
bridge.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i = 0; i < events.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
bridge.cpp:90:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for (int j = i+1; j < events.size(); j++)
      |                           ~~^~~~~~~~~~~~~~~
bridge.cpp:97:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             for (int k = 0; k < events.size(); k++)
      |                             ~~^~~~~~~~~~~~~~~
bridge.cpp:118:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |             for (int k = 0; k < events.size(); k++)
      |                             ~~^~~~~~~~~~~~~~~
bridge.cpp:139:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |             for (int k = 0; k < events.size(); k++)
      |                             ~~^~~~~~~~~~~~~~~
bridge.cpp:160:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |             for (int k = 0; k < events.size(); k++)
      |                             ~~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 416 KB Output is correct
12 Correct 29 ms 4980 KB Output is correct
13 Correct 52 ms 4980 KB Output is correct
14 Correct 42 ms 4980 KB Output is correct
15 Correct 31 ms 3064 KB Output is correct
16 Correct 34 ms 4980 KB Output is correct
17 Correct 37 ms 4980 KB Output is correct
18 Correct 43 ms 4980 KB Output is correct
19 Correct 50 ms 4980 KB Output is correct
20 Correct 38 ms 4980 KB Output is correct
21 Correct 48 ms 4980 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 11 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 8 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 9 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Execution timed out 2044 ms 384 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 7 ms 416 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 10 ms 288 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Execution timed out 2058 ms 384 KB Time limit exceeded
14 Halted 0 ms 0 KB -