Submission #1142932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142932		ILoveSabnaj	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	7 ms	428 KiB

bridge

    #include <bits/stdc++.h>
    using namespace std;

    signed main() {
        int n, q;    
        cin >> n >> q;
        struct Node{
            char A, B;
            int P1, P2;
            Node(int a, int b, int p1, int p2) : A{a}, B{b}, P1{p1}, P2{p2} {}
        };
        vector<Node> citizens;
        int sum = 0;
        set<int> Bridges;
        for (int i = 0; i < q; i++) {
            char a, b;
            int p1, p2;
            cin >> a >> p1 >> b >> p2;
            Bridges.insert(p1);
            Bridges.insert(p2);
            if (a == b) {
                sum += abs(p2 - p1);
            } else {
                citizens.push_back(Node(a, b, p1, p2));
            }
        }
        int ans = 1e18;
        if (n == 1) {
            for (int i : Bridges) {
                int dis = 0;
                for (Node c : citizens) {
                    int A = abs(i - c.P1);
                    int B = abs(i - c.P2);
                    dis += (A + B + 1);
                }
                ans = min(ans, dis);
            }
        } else {
            for (int i : Bridges) {
                for (int j : Bridges) {
                    if (i == j) continue;

                    int dis = 0;
                    for (Node c : citizens) {
                        int A1 = abs(i - c.P1);
                        int B1 = abs(i - c.P2);

                        int A2 = abs(j - c.P1);
                        int B2 = abs(j - c.P2);
                        dis += (min(A1 + B1, A2 + B2) + 1);
                    }
                    ans = min(ans, dis);
                }
            }
        }
        cout << ans + sum << endl;
        return 0;
    }
    /*
        0   1   2   3   4   5   6   7   8   9   10
    ------------------------------------------------------------
    A   -   -   -   -   1   3   -   5   -   -   -   -   -   -   
                    | |      
    B   1   2   4   2   -   -   4   3   -   -   -   -   -   -   
        5   -   -   -   -   -   -   -   -   -   -   -   -   -   
    */

Compilation message (stderr)

bridge.cpp: In constructor 'main()::Node::Node(int, int, int, int)':
bridge.cpp:10:52: warning: narrowing conversion of 'a' from 'int' to 'char' [-Wnarrowing]
   10 |             Node(int a, int b, int p1, int p2) : A{a}, B{b}, P1{p1}, P2{p2} {}
      |                                                    ^
bridge.cpp:10:58: warning: narrowing conversion of 'b' from 'int' to 'char' [-Wnarrowing]
   10 |             Node(int a, int b, int p1, int p2) : A{a}, B{b}, P1{p1}, P2{p2} {}
      |                                                          ^
bridge.cpp: In function 'int main()':
bridge.cpp:27:19: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   27 |         int ans = 1e18;
      |                   ^~~~

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