Submission #35134209

---

Source Code Expand

#include <bits/stdc++.h>



using namespace std;


// #pragma gcc optimize("ofast")
// #pragma gcc target("avx,avx2,fma")


#define int long long

#define all(x) (x).begin(), (x).end()


#define pb push_back
#define endl '\n'
#define fi first
#define se second

// const int mod = 1e9 + 7;

const int mod=998'244'353;


const long long INF = 2e18 + 10;
// const int INF=4e9+10;

#define readv(x, n)   \
    vector<int> x(n); \
    for (auto &i : x) \
        cin >> i;



template <typename t>
    using v = vector<t>;

template <typename t>
    using vv = vector<vector<t>>;

template <typename t>
    using vvv = vector<vector<vector<t>>>;

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<vector<vector<vector<int>>>> vvvvi;
typedef vector<vector<double>> vvd;

typedef pair<int, int> pii;



int multiply(int a, int b, int in_mod) { return (int)(1ll * a * b % in_mod); }
int mult_identity(int a) { return 1; }



const double pi = acosl(-1);



auto power(auto a, auto b, const int in_mod)
{

    auto prod = mult_identity(a);
    auto mult = a % in_mod;
    while (b != 0)
    {
        if (b % 2)
        {
            prod = multiply(prod, mult, in_mod);
        }
        if(b/2)
        mult = multiply(mult, mult, in_mod);
        b /= 2;
    }

    return prod;
}
auto mod_inv(auto q, const int in_mod)
{
    return power(q, in_mod - 2, in_mod);
}


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());



#define stp cout << fixed << setprecision(20);



struct DSU {
    std::vector<int> f, siz;
    DSU(int n) : f(n), siz(n, 1) { std::iota(f.begin(), f.end(), 0); }
    int leader(int x) {
        while (x != f[x]) x = f[x] = f[f[x]];
        return x;
    }
    bool same(int x, int y) { return leader(x) == leader(y); }
    bool merge(int x, int y) {
        x = leader(x);
        y = leader(y);

        if (x == y) return false;

        if(siz[x]< siz[y])
            swap(x,y);

        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    int size(int x) { return siz[leader(x)]; }
};

void solv(){
    int n, m;
    cin>>n>>m;

    readv(x,n);
    readv(y,n);
    x.insert(x.begin(),0);
    y.insert(y.begin(),0);

    v<tuple<int, int, int>> edges;
    for(int i = 0;i<m;i++){
        int a, b, z;
        cin>>a>>b>>z;
        edges.emplace_back(z, a, b);
    }
    sort(all(edges));
    DSU uf(n+ 1);


    vi mn(n + 1);
    for(int i =1 ;i<=n;i++)
        mn[i] = min(x[i], y[i]);
    multiset<int> mn_diff;

    for(int i =1 ;i<=n;i++){
        mn_diff.insert(max(x[i],y[i]));
    }
    int mn_sm = 0;
    for(auto i:mn)
        mn_sm += i;

    int x_sm = accumulate(all(x), (int)0);
    int y_sm = accumulate(all(y), (int)0);
    int  ans = INF;


    ans = mn_sm + *mn_diff.begin();
    ans = min(ans, x_sm);
    ans = min(ans, y_sm);


    int running_cost = 0;
    int comps = n;
    if(comps == 1)
        ans = min(ans, (int)0);
    for(auto [z, a, b]:edges){

        a = uf.leader(a);
        b = uf.leader(b);
        if(a == b)
            continue;
        comps--;


        mn_sm -= mn[a];
        mn_sm -= mn[b];

        mn_diff.erase(mn_diff.find(max(x[a] , y[a])));
        mn_diff.erase(mn_diff.find(max(x[b] , y[b])));


        int new_x = min(x[a], x[b]);
        int new_y = min(y[a], y[b]);
        x_sm -= x[a];
        y_sm -= y[a];
        
        x_sm -= x[b];
        y_sm -= y[b];

        uf.merge(a,b);
        a = uf.leader(a);
        mn[a] = min(new_y, new_x);
        x[a] = new_x;
        y[a] = new_y;
        x_sm += x[a];
        y_sm += y[a];
        mn_diff.insert(max(x[a] , y[a]));

        running_cost += z;

        mn_sm += mn[a];

        // mn_diff.erase(mn_diff.find(abs(x[a] - y[a])));

        int cst = running_cost + mn_sm;
        if(mn_diff.size())
            cst += *mn_diff.begin();
        ans = min(ans, cst);

        ans = min(ans, running_cost + x_sm);
        ans = min(ans, running_cost + y_sm);

        if(comps == 1){
            ans = min(ans, running_cost);
        }





    }
    cout<<ans<<endl;
}

void solve()
{

    int t = 1;
    // cin>>t;
    for(int T=1;T<=t;T++)
    {
        // cout<<"Case #"<<T<<": ";
        solv();
    }
}




signed main()
{

    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);


    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cerr.tie(NULL);

    auto clk = clock();
    // -------------------------------------Code starts here---------------------------------------------------------------------

    signed t = 1;
    // cin >> t;

    for (signed test = 1; test <= t; test++)
    {
        // cout<<"Case #"<<test<<": ";

        solve();
    }

    // -------------------------------------Code ends here------------------------------------------------------------------

    clk = clock() - clk;

    #ifndef ONLINE_JUDGE
    cerr << fixed << setprecision(6) << "\nTime: " << ((float)clk) / CLOCKS_PER_SEC << "\n";
    #endif
    return 0;
}

/*
000100

1000100

1 0 -1 -2 -1 -2 -3
*/

Submission Info

Compile Error

./Main.cpp: In function ‘long long int mult_identity(long long int)’:
./Main.cpp:58:23: warning: unused parameter ‘a’ [-Wunused-parameter]
   58 | int mult_identity(int a) { return 1; }
      |                       ^
./Main.cpp: At global scope:
./Main.cpp:66:12: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts’
   66 | auto power(auto a, auto b, const int in_mod)
      |            ^~~~
./Main.cpp:66:20: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts’
   66 | auto power(auto a, auto b, const int in_mod)
      |                    ^~~~
./Main.cpp:84:14: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts’
   84 | auto mod_inv(auto q, const int in_mod)
      |              ^~~~

Judge Result