oj.uz

Submission #566635

# Submission time Handle Problem Language Result Execution time Memory
566635 2022-05-22T13:32:42 Z ac2hu Palembang Bridges (APIO15_bridge) C++14
22 / 100
 152 ms 13616 KB 
#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else 
#define deb(x...)
#endif
using namespace std;
#define int long long 
signed main() {
    iostream::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int n,k;cin >> k >> n;
    vector<pair<int,int>> loc;
    int same_part = 0;
    vector<int> s;
    for(int i = 0;i<n;i++){
        char c1, c2;
        int a,b;
        cin >> c1 >> a >> c2 >> b;
        if(c1 == c2){
            same_part += abs(a - b);
        }
        else{
            s.push_back(a);
            s.push_back(b);
            s.push_back(a - 1);
            s.push_back(b - 1);
            same_part++;
            if(a > b)swap(a, b);
            loc.emplace_back(a, b);
        }
    }
    s.push_back(0);
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
    deb(loc);
    multiset<pair<int,int>> aset, bset;
    for(auto e : loc)aset.insert(e);
    int ans = 1e18;
    int sump1 = 0;
    int sump2 = 0;
    int sump3 = 0;
    int inp2 = 0;
    for(auto e : aset)sump1 += e.first + e.second;
    for(auto i : s){
        while(aset.size() > 0){
            auto it = *aset.begin();
            if(i >= it.first){
                bset.insert({it.second, it.first});
                aset.erase(aset.begin());
                sump1 -= it.first + it.second;
                sump3 += abs(it.first - it.second);
            }
            else
                break;
        }
        while(bset.size() > 0){
            auto it = *bset.begin();
            if(i >= it.first){
                bset.erase(bset.begin());
                sump2 += it.first + it.second;
                sump3 -= abs(it.first - it.second);
                inp2++;
            }
            else break;
        }
        deb(aset, bset);
        int p1 = sump1 - 2*i*aset.size();
        int p2 = inp2*2*i - sump2;
        deb(same_part, p1, p2, sump3);
        ans = min(ans, same_part + (sump1 - 2*i*(int)aset.size()) + (inp2*2*i - sump2) + sump3);
    }
    cout << ans << "\n";
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:68:13: warning: unused variable 'p1' [-Wunused-variable]
   68 |         int p1 = sump1 - 2*i*aset.size();
      |             ^~
bridge.cpp:69:13: warning: unused variable 'p2' [-Wunused-variable]
   69 |         int p2 = inp2*2*i - sump2;
      |             ^~

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 66 ms 12060 KB Output is correct
13 Correct 152 ms 13520 KB Output is correct
14 Correct 131 ms 11316 KB Output is correct
15 Correct 77 ms 8040 KB Output is correct
16 Correct 74 ms 12880 KB Output is correct
17 Correct 98 ms 13616 KB Output is correct
18 Correct 103 ms 13232 KB Output is correct
19 Correct 126 ms 13568 KB Output is correct
20 Correct 66 ms 13096 KB Output is correct
21 Correct 79 ms 13244 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -