Submission #1062071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062071		Ausp3x	Wiring (IOI17_wiring)	C++17	7 / 100	20 ms	3096 KiB

wiring

// 人外有人，天外有天
// author: Ausp3x

#pragma GCC optimize("O1, O2, O3, Ofast, unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include "wiring.h"
using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define pb push_back
// #define DEBUG
typedef long long    lng;
template<class T> 
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int const INF32 = 0x3f3f3f3f;
lng const INF64 = 0x3f3f3f3f3f3f3f3f;

struct UnionFind {
    int n;
    vector<int> link, node_size, edge_size;

    UnionFind(int n): n(n) {
        link.resize(n + 1);
        iota(link.begin(), link.end(), 0);
        node_size.resize(n + 1, 1);
        edge_size.resize(n + 1);
    }

    int findSet(int v) {
        if (v == link[v]) {
            return link[v];
        }
            
        return link[v] = findSet(link[v]);
    }

    bool isSameSet(int a, int b) {
        return findSet(a) == findSet(b);
    }

    void uniteSets(int a, int b) {
        a = findSet(a);
        b = findSet(b);
        if (node_size[a] < node_size[b]) {
            swap(a, b);
        }

        if (a == b) {
            edge_size[a]++;
            return;
        }

        node_size[a] += node_size[b];
        edge_size[a] += edge_size[b] + 1;
        link[b] = a;

        return;
    }

    void debugPrint() {
        cout << n << endl;
        cout << "link:" << endl;
        for (int x : link)
            cout << x << ' ';
        cout << endl;
        cout << "node_size:" << endl;
        for (int x : node_size)
            cout << x << ' ';
        cout << endl;
        cout << "edge_size:" << endl;
        for (int x : edge_size)
            cout << x << ' ';
        cout << endl;

        return;
    }
};

vector<int> st1_R, st1_B;
vector<vector<lng>> memo;
lng st1_dp(int i, int j) {
    if (i < 0 || j < 0)
        return INF64;

    if (memo[i][j] != INF64)
        return memo[i][j];
    
    if (i == 0 && j == 0)
        return memo[i][j] = abs(st1_R[i] - st1_B[j]);

    return memo[i][j] = min(min({st1_dp(i - 1, j), st1_dp(i, j - 1), st1_dp(i - 1, j - 1)}) + abs(st1_R[i] - st1_B[j]), INF64);
}

lng min_total_length(vector<int> R, vector<int> B) {
    int n = R.size(), m = B.size();
    
    if (n <= 200 && m <= 200) {
        st1_R = R;
        st1_B = B;
        memo.resize(n, vector<lng>(m, INF64));

        // st1_dp(n - 1, m - 1);

        // for (int i = 0; i < n; i++) {
        //     for (int j = 0; j < m; j++)
        //         cout << memo[i][j] << ' ';
        //     cout << endl;
        // }

        return st1_dp(n - 1, m - 1);
    }

    return -1;
}

#ifdef DEBUG
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<int> R(n);
        for (int &r : R)
            cin >> r;
        vector<int> B(m);
        for (int &b : B)
            cin >> b;

        cout << min_total_length(R, B) << endl;
    }

    return 0;
}
#endif

Compilation message (stderr)

wiring.cpp:4:55: warning: bad option '-f O2' to pragma 'optimize' [-Wpragmas]
    4 | #pragma GCC optimize("O1, O2, O3, Ofast, unroll-loops")
      |                                                       ^
wiring.cpp:4:55: warning: bad option '-f O3' to pragma 'optimize' [-Wpragmas]
wiring.cpp:4:55: warning: bad option '-f Ofast' to pragma 'optimize' [-Wpragmas]
wiring.cpp:4:55: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
In file included from wiring.cpp:7:
wiring.h:3:66: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
    3 | long long min_total_length(std::vector<int> r, std::vector<int> b);
      |                                                                  ^
wiring.h:3:66: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
wiring.h:3:66: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
wiring.h:3:66: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
wiring.h:3:66: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
wiring.h:3:66: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
wiring.h:3:66: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
wiring.h:3:66: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
wiring.cpp:26:20: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   26 |     UnionFind(int n): n(n) {
      |                    ^
wiring.cpp:26:20: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
wiring.cpp:26:20: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
wiring.cpp:26:20: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
wiring.cpp:33:22: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   33 |     int findSet(int v) {
      |                      ^
wiring.cpp:33:22: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
wiring.cpp:33:22: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
wiring.cpp:33:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
wiring.cpp:41:32: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   41 |     bool isSameSet(int a, int b) {
      |                                ^
wiring.cpp:41:32: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
wiring.cpp:41:32: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
wiring.cpp:41:32: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
wiring.cpp:45:32: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   45 |     void uniteSets(int a, int b) {
      |                                ^
wiring.cpp:45:32: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
wiring.cpp:45:32: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
wiring.cpp:45:32: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
wiring.cpp:64:21: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   64 |     void debugPrint() {
      |                     ^
wiring.cpp:64:21: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
wiring.cpp:64:21: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
wiring.cpp:64:21: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
wiring.cpp:85:24: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   85 | lng st1_dp(int i, int j) {
      |                        ^
wiring.cpp:85:24: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
wiring.cpp:85:24: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
wiring.cpp:85:24: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
wiring.cpp:98:50: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   98 | lng min_total_length(vector<int> R, vector<int> B) {
      |                                                  ^
wiring.cpp:98:50: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
wiring.cpp:98:50: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
wiring.cpp:98:50: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]

• Subtask 1: 7 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45