Submission #602376

#	Time	Username	Problem	Language	Result	Execution time	Memory
602376		verngutz	Arcade (NOI20_arcade)	C++17	51 / 100	1094 ms	180844 KiB

Arcade

#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
template <typename X, typename Y> istream& operator>>(istream& is, pair<X, Y>& p) { return is >> p.first >> p.second; }
template <bool Index> struct graph {
    int L, R;
    vector<vector<int>> adj;
    graph(int L, int R) : L(L), R(R), adj(L + Index) {}
    void add_edge(int u, int v) {
        adj[u].push_back(v);
    }
};
template <bool Index> vector<int> max_matching(graph<Index>& g) {
    vector<bool> matched(g.L + Index);
    vector<int> partner(g.R + Index, -1), d(g.L + Index), adj_ptr(g.L + Index);
    auto make_level_graph = [&]() {
        fill(d.begin(), d.end(), -1);
        queue<int> q;
        for(int u = Index; u < matched.size(); u++) {
            if(not matched[u]) {
                d[u] = 0;
                q.push(u);
            }
        }
        bool has_unmatched = false;
        while(not q.empty()) {
            int u = q.front(); q.pop();
            for(int v : g.adj[u]) {
                if(partner[v] == -1) {
                    has_unmatched = true;
                } else if(d[partner[v]] == -1) {
                    d[partner[v]] = d[u] + 1;
                    q.push(partner[v]);
                }
            }
        }
        return has_unmatched;
    };
    function<bool(int)> find_alt_path = [&](int u) {
        for(int& i = adj_ptr[u]; i < g.adj[u].size(); i++) {
            int v = g.adj[u][i];
            if(partner[v] == -1 or (d[partner[v]] == d[u] + 1 and find_alt_path(partner[v]))) {
                partner[v] = u;
                return true;
            }
        }
        return false;
    };
    while(make_level_graph()) {
        fill(adj_ptr.begin(), adj_ptr.end(), 0);
        for(int u = Index; u < matched.size(); u++) {
            if(not matched[u] and find_alt_path(u)) {
                matched[u] = true;
            }
        }
    }
    auto find_vertex_cover = [&]() {
        vector<int> coverL(g.L + Index), coverR(g.R + Index);
        for(int u = Index; u < coverL.size(); u++) {
            coverL[u] = d[u] == -1;
        }
        for(int v = Index; v < coverR.size(); v++) {
            coverR[v] = partner[v] != -1 and not coverL[partner[v]];
        }
    };
    return partner;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> t(m), a(m);
    cin >> t >> a;
    graph<0> g(m, m);
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < m; j++) {
            if(i != j and t[j] > t[i] and abs(t[j] - t[i]) >= abs(a[j] - a[i])) {
                g.add_edge(i, j);
            }
        }
    }
    auto matching = max_matching(g);
    cout << count(matching.begin(), matching.end(), -1) << endl;
    return 0;
}

Compilation message (stderr)

Arcade.cpp: In lambda function:
Arcade.cpp:66:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int u = Index; u < coverL.size(); u++) {
      |                            ~~^~~~~~~~~~~~~~~
Arcade.cpp:69:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(int v = Index; v < coverR.size(); v++) {
      |                            ~~^~~~~~~~~~~~~~~
Arcade.cpp: In instantiation of 'std::vector<int> max_matching(graph<Index>&) [with bool Index = false]':
Arcade.cpp:90:35:   required from here
Arcade.cpp:26:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int u = Index; u < matched.size(); u++) {
      |                            ~~^~~~~~~~~~~~~~~~
Arcade.cpp:47:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for(int& i = adj_ptr[u]; i < g.adj[u].size(); i++) {
      |                                  ~~^~~~~~~~~~~~~~~~~
Arcade.cpp:58:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for(int u = Index; u < matched.size(); u++) {
      |                            ~~^~~~~~~~~~~~~~~~
Arcade.cpp:66:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int u = Index; u < coverL.size(); u++) {
      |                            ~~^~~~~~~~~~~~~~~
Arcade.cpp:69:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(int v = Index; v < coverR.size(); v++) {
      |                            ~~^~~~~~~~~~~~~~~
Arcade.cpp:64:10: warning: variable 'find_vertex_cover' set but not used [-Wunused-but-set-variable]
   64 |     auto find_vertex_cover = [&]() {
      |          ^~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 0 / 14
• Subtask 6: 0 / 20
• Subtask 7: 0 / 15