Submission #685185

#	Time	Username	Problem	Language	Result	Execution time	Memory
685185		omikron123	Palembang Bridges (APIO15_bridge)	C++14	31 / 100	2074 ms	2608 KiB

bridge

// https://oj.uz/problem/view/APIO15_bridge

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;

// K=1,2, N=1e5
// 1. 家和办公室在同一边的是不参与计算的，和桥没有关系。
// 2. 最小值都在event点上面取得，而且是一个U型的阶梯函数，所以应该可以固定一个桥的位置，然后binary search另外一个。
// 3. 进一步可以发现K=1的时候，答案就是S[i], T[i]的median. 
// 4. K=2的时候，简单做法是可以暴力搜索O(n^2)，这已经可以得2/3的分了。
// 5. 

int n, K;
ll ans;
vector<pair<int,int>> x;

int main() {
    scanf("%d %d", &K, &n);
    for (int i = 0; i < n; i++) {
        char c1[10], c2[10];
        int x1, x2;
        scanf("%s %d %s %d", c1, &x1, c2, &x2);
        if (c1[0] == c2[0]) ans += abs(x1-x2);
        else x.push_back({min(x1,x2), max(x1,x2)});
    }

    vector<int> X;
    for (auto p: x) {
        X.push_back(p.first);
        X.push_back(p.second);
    }
    sort(X.begin(), X.end());
    if (K == 1 && x.size()) {
        // just return the median of all numbers
        int m = X[X.size() / 2];
        for (auto p: x) {
            ans += abs(p.first-m) + abs(p.second-m) + 1;
        }
    } else if (K==2 && x.size()) {
        // brute-force all pairs of roads
        ll ans2 = 1e18;
        for (int i = 0; i < X.size(); i++)
            for (int j = i+1; j < X.size(); j++) {
                int r1 = X[i], r2 = X[j];
                ll sum = 0;
                for (auto p: x) {
                    sum += min(abs(p.first-r1)+abs(p.second-r1), abs(p.first-r2)+abs(p.second-r2)) + 1;
                }
                ans2 = min(ans2, sum);
            }
        ans += ans2;
    }

    printf("%lld", ans);

    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:48:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for (int i = 0; i < X.size(); i++)
      |                         ~~^~~~~~~~~~
bridge.cpp:49:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             for (int j = i+1; j < X.size(); j++) {
      |                               ~~^~~~~~~~~~
bridge.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%d %d", &K, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf("%s %d %s %d", c1, &x1, c2, &x2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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