oj.uz

답안 #685185

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
685185 2023-01-23T16:36:07 Z omikron123 Palembang Bridges (APIO15_bridge) C++14
31 / 100
 2000 ms 2608 KB 
// 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

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.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 30 ms 2496 KB Output is correct
13 Correct 48 ms 2496 KB Output is correct
14 Correct 36 ms 2480 KB Output is correct
15 Correct 28 ms 1472 KB Output is correct
16 Correct 33 ms 2548 KB Output is correct
17 Correct 36 ms 2500 KB Output is correct
18 Correct 41 ms 2500 KB Output is correct
19 Correct 46 ms 2532 KB Output is correct
20 Correct 36 ms 2608 KB Output is correct
21 Correct 49 ms 2592 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 224 KB Output is correct
2 Correct 0 ms 224 KB Output is correct
3 Correct 4 ms 224 KB Output is correct
4 Correct 6 ms 300 KB Output is correct
5 Correct 2 ms 300 KB Output is correct
6 Correct 0 ms 224 KB Output is correct
7 Correct 6 ms 224 KB Output is correct
8 Correct 6 ms 224 KB Output is correct
9 Correct 6 ms 224 KB Output is correct
10 Correct 6 ms 216 KB Output is correct
11 Correct 6 ms 212 KB Output is correct
12 Correct 6 ms 212 KB Output is correct

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 7 ms 212 KB Output is correct
4 Correct 5 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 6 ms 284 KB Output is correct
8 Correct 6 ms 212 KB Output is correct
9 Correct 6 ms 212 KB Output is correct
10 Correct 6 ms 212 KB Output is correct
11 Correct 6 ms 288 KB Output is correct
12 Correct 6 ms 276 KB Output is correct
13 Execution timed out 2065 ms 256 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 5 ms 212 KB Output is correct
4 Correct 5 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 6 ms 292 KB Output is correct
8 Correct 6 ms 288 KB Output is correct
9 Correct 6 ms 284 KB Output is correct
10 Correct 6 ms 212 KB Output is correct
11 Correct 7 ms 288 KB Output is correct
12 Correct 6 ms 216 KB Output is correct
13 Execution timed out 2074 ms 212 KB Time limit exceeded
14 Halted 0 ms 0 KB -