Submission #1122322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122322		Hamed_Ghaffari	Toll (APIO13_toll)	C++17	100 / 100	1240 ms	8268 KiB

toll

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

using ll  = long long;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using ull = unsigned long long;

#define X               first
#define Y               second
#define SZ(x)           int(x.size())
#define all(x)          x.begin(), x.end()
#define mins(a,b)       (a = min(a,b))
#define maxs(a,b)       (a = max(a,b))
#define pb              push_back
#define Mp              make_pair
#define lc              id<<1
#define rc              lc|1
#define mid             ((l+r)/2)
mt19937_64              rng(chrono::steady_clock::now().time_since_epoch().count());

const ll  INF = 1e9 + 23;
const ll  MOD = 1e9 + 7;
const int MXN = 1e5 + 5;
const int LOG = 23;

struct DSU {
    int par[MXN], sz[MXN];
    void init(int n) {
        iota(par, par+n, 0);
        fill(sz, sz+n, 1);
    }
    int Find(int v) {
        return v==par[v] ? v : par[v]=Find(par[v]);
    }
    bool Union(int u, int v) {
        if((u=Find(u))==(v=Find(v))) return 0;
        if(sz[u]<sz[v]) swap(u,v);
        sz[par[v]=u] += sz[v];
        return 1;
    }
} dsu, comp;

int n, m, k, name[MXN], N;
ll p[MXN], sum[MXN];

vector<pair<int,bool>> g[MXN];
int hi[MXN], lim[MXN], par[MXN];
ll ans, cur;

void add_edge(int u, int v, bool nw) {
    g[u].pb(Mp(v, nw));
    g[v].pb(Mp(u, nw));
}

void dfs1(int v) {
    sum[v] = p[v];
    for(auto [u, nw] : g[v])
        if(u!=par[v]) {
            hi[u] = hi[v]+1;
            par[u] = v;
            dfs1(u);
            sum[v] += sum[u];
        }
}

void limit(int u, int v, int w) {
    if(hi[u]<hi[v]) swap(u,v);
    while(hi[u]>hi[v]) {
        mins(lim[u], w);
        u = par[u];
    }
    while(u!=v) {
        mins(lim[u], w);
        mins(lim[v], w);
        u = par[u];
        v = par[v];
    }
}

void dfs2(int v) {
    for(auto [u, nw] : g[v])
        if(u!=par[v]) {
            if(nw) cur += sum[u]*lim[u];
            dfs2(u);
        }
}

void Main() {
    cin >> n >> m >> k;
    vector<pair<int, pii>> E(m);
    for(auto &e : E) cin >> e.Y.X >> e.Y.Y >> e.X, e.Y.X--, e.Y.Y--;
    sort(all(E));
    dsu.init(n);
    comp.init(n);
    vector<pii> E2(k);
    for(auto &e : E2) {
        cin >> e.X >> e.Y; e.X--, e.Y--;
        dsu.Union(e.X, e.Y);
    }
    for(auto e : E)
        if(dsu.Union(e.Y.X, e.Y.Y))
            comp.Union(e.Y.X, e.Y.Y);
    memset(name, -1, sizeof(name));
    for(int v=0, pp; v<n; v++) {
        int vv = comp.Find(v);
        if(name[vv]==-1) name[vv] = N++;
        cin >> pp;
        p[name[vv]] += pp;
    }
    for(auto &e : E2) {
        e.X = name[comp.Find(e.X)];
        e.Y = name[comp.Find(e.Y)];
    }
    dsu.init(N);
    vector<pair<int, pii>> EE;
    for(auto e : E) {
        int w = e.X;
        int u = name[comp.Find(e.Y.X)];
        int v = name[comp.Find(e.Y.Y)];
        if(dsu.Union(u,v)) EE.pb(Mp(w, Mp(u,v)));
    }
    for(int msk=1; msk<(1<<k); msk++) {
        dsu.init(N);
        bool cy=0;
        for(int i=0; i<k; i++)
            if(msk>>i & 1)
                cy |= !dsu.Union(E2[i].X, E2[i].Y);
        if(cy) continue;
        for(int i=0; i<k; i++)
            if(msk>>i & 1)
                add_edge(E2[i].X, E2[i].Y, 1);
        vector<pair<int, pii>> lim_E;
        for(auto e : EE)
            if(dsu.Union(e.Y.X, e.Y.Y))
                add_edge(e.Y.X, e.Y.Y, 0);
            else lim_E.pb(e);
        for(int v=0; v<N; v++) lim[v] = 1e9;
        dfs1(0);
        for(auto e : lim_E) limit(e.Y.X, e.Y.Y, e.X);
        cur = 0;
        dfs2(0);
        maxs(ans, cur);
        for(int v=0; v<N; v++) g[v].clear();
    }
    cout << ans << '\n';
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int T = 1;
    // cin >> T;
    while(T--) Main();
    return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 22 / 22