Submission #57468702

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using pl = pair<ll, ll>;
constexpr ll INF = 1e16 + 7;
constexpr ll mod = 1e9 + 7;
constexpr ld eps = 1e-9;
const ld PI = acos(-1);

vector<int> z_function(const string &s) {
    int n = s.size();
    vector<int> z(n);
    z[0] = 0;
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i < r) {
            z[i] = min(r - i, z[i - l]);
        }
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if (i + z[i] > r) {
            r = i + z[i];
            l = i;
        }
    }
    return z;
}

struct Dinic {

    struct edge {
        ll from, to;
        ll cap, flow;
    };
    ll n;

    vector<vector<ll>> g;
    vector<edge> E;

    Dinic(ll n) : n(n) {
        g.resize(n);
    }

    void addEdge(ll from, ll to, ll cap) {
        g[from].push_back(E.size());
        E.push_back({from, to, cap, 0});
        g[to].push_back(E.size());
        E.push_back({to, from, 0, 0});
    }

    vector<ll> bfs(ll st, ll mn) {
        ll n = g.size();
        vector<ll> d(n, -1);
        d[st] = 0;
        queue<ll> q;
        q.push(st);
        while (!q.empty()) {
            ll v = q.front();
            q.pop();
            for (const auto ind: g[v]) {
                ll to = E[ind].to;
                if (d[to] == -1 && E[ind].cap - E[ind].flow >= mn) {
                    d[to] = d[v] + 1;
                    q.push(to);
                }
            }
        }

        return d;
    }

    ll solve(ll st, ll en) {
        ll res = 0;
        for (ll i = 29; i >= 0; --i) {
            while (1) {
                vector<ll> d = bfs(st, (1ll << i));
                if (d[en] == -1)break;
                vector<ll> ptr(g.size(), 0);
                while (ll add = dfs(st, INF, (1ll << i), en, d, ptr)) {
                    res += add;
                }
            }
        }
        return res;
    }

    ll dfs(ll v, ll flow, const ll mn, const ll end, const vector<ll> &d, vector<ll> &ptr) {
        if (flow < mn) {
            return 0;
        }
        if (v == end) {
            return flow;
        }
        for (; ptr[v] < g[v].size(); ++ptr[v]) {
            ll ind = g[v][ptr[v]];
            ll to = E[ind].to;
            if (d[to] != d[v] + 1)continue;
            if (ll add = dfs(to, min(flow, E[ind].cap - E[ind].flow), mn, end, d, ptr)) {
                E[ind].flow += add;
                E[ind ^ 1].flow -= add;
                return add;
            }
        }
        return 0;
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    vector<string> a(n);
    for (auto &i: a)cin >> i;
    vector<ll> w(n);
    for (auto &i: w) {
        cin >> i;
    }
    {
        map<string, ll> best;
        for (int i = 0; i < n; ++i) {
            best[a[i]] = max(best[a[i]], w[i]);
        }
        a.clear();
        w.clear();
        for(auto &[x,y] : best){
            a.push_back(x);
            w.push_back(y);
        }
        n = a.size();
    }
    ll res = 0;
    for(auto x : w)res+=x;
    int st = 0, en = 2 * n + 1;
    Dinic sol(en + 1);
    for (int i = 0; i < n; ++i) {
        sol.addEdge(st, i + 1, w[i]);
        sol.addEdge(i + 1 + n, en, w[i]);
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j)continue;
            auto z = z_function(a[j] + '#' + a[i]);
            if (*max_element(z.begin(), z.end()) == a[j].size()) {
                sol.addEdge(j + 1, i + 1 + n, INF);
            }
        }
    }
    cout << res - sol.solve(st, en);
}

Submission Info

Compile Error

Main.cpp: In member function ‘ll Dinic::dfs(ll, ll, ll, ll, const std::vector<long long int>&, std::vector<long long int>&)’:
Main.cpp:98:23: warning: comparison of integer expressions of different signedness: ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type’ {aka ‘long long int’} and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   98 |         for (; ptr[v] < g[v].size(); ++ptr[v]) {
Main.cpp: In function ‘int main()’:
Main.cpp:147:50: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  147 |             if (*max_element(z.begin(), z.end()) == a[j].size()) {
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Judge Result