Submission #1217095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217095		Zero_OP	Toll (APIO13_toll)	C++20	16 / 100	4 ms	7492 KiB

toll

#include <bits/stdc++.h>

using namespace std;

//loops (warning : long long)
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r - 1); i >= l; --i)
#define rep(i, l, r) for(int i = (l); i < (r); ++i)

//pairs, tuples
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

//vectors
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sum_of(v) accumulate(all(v), 0ll)
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))

//binary search
#define lwb lower_bound
#define upb upper_bound

//other stuffs
#define dbg(x) "[" #x " = " << (x) << "]"
#define file(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }

template<typename T>
bool minimize(T& a, const T& b){
    if(a > b) return a = b, true;
    return false;
}

template<typename T>
bool maximize(T& a, const T& b){
    if(a < b) return a = b, true;
    return false;
}

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using db = double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;

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

const int MAX = 1e5 + 5;

struct edge{
    int u, v, w;
    bool operator < (const edge& o) const {
        return w < o.w;
    }
} base[MAX], additional[20];

int N, M, K, weight[20];
int s[MAX];
int vis[MAX], lab[MAX];
vi g[MAX];
vpi adj[MAX], adj_mst[MAX];
int up[MAX], up_edge[MAX], depth[MAX];

ll sum[MAX], dp[MAX];

void dfs_dp(int u, int p, int q){
    sum[u] = s[u];
    dp[u] = 0;
    for(auto [id, t] : adj[u]) if(id != p || t != q){
        if(t == -1){
            int v = additional[id].u ^ additional[id].v ^ u;
            // cout << dbg(u) << dbg(v) << '\n';
            dfs_dp(v, id, t);
            dp[u] += dp[v];
            sum[u] += sum[v];
            dp[u] += sum[v] * weight[id];
            // cout << dbg(sum[v]) << dbg(weight[id]) << dbg(id) << '\n';
        } else{
            int v = base[id].u ^ base[id].v ^ u;
            // cout << dbg(u) << dbg(v) << '\n';
            dfs_dp(v, id, t);
            dp[u] += dp[v];
            sum[u] += sum[v];
        }
    }
    adj[u].clear();
}

void dfs_mst(int u, int p){
    for(auto [v, w] : adj_mst[u]) if(v != p){
        up[v] = u;
        up_edge[v] = w;
        depth[v] = depth[u] + 1;
        dfs_mst(v, u);
    }
}

int get_max(int u, int v){
    int ans = 0;
    if(depth[u] < depth[v]) swap(u, v);
    while(depth[u] > depth[v]){
        maximize(ans, up_edge[u]);
        u = up[u];
    }

    if(u == v) return ans;
    while(u != v){
        maximize(ans, up_edge[u]);
        maximize(ans, up_edge[v]);
        u = up[u]; v = up[v];
    }
    return ans;
}

int root(int u){
    return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
}

bool join(int u, int v){
    u = root(u);
    v = root(v);
    if(u == v) return false;
    if(lab[u] > lab[v]) swap(u, v);
    lab[u] += lab[v]; lab[v] = u;
    return true;
}

bool dfs(int u, int p, int tm){
    vis[u] = tm;
    for(auto v : g[u]) if(v != p){
        if(vis[v] == tm) return true;
        if(dfs(v, u, tm)) return true;
    }
    return false;
}

void testcase(int ntestcase){
    cin >> N >> M >> K;
    for(int i = 0; i < M; ++i) cin >> base[i].u >> base[i].v >> base[i].w;


    vector<int> nodes;
    for(int i = 0; i < K; ++i) {
        cin >> additional[i].u >> additional[i].v;
        nodes.pb(additional[i].u);
        nodes.pb(additional[i].v);
    }

    for(int i = 1; i <= N; ++i) cin >> s[i];

    sort(all(nodes)); compact(nodes);
    sort(base, base + M);

    fill(lab + 1, lab + N + 1, -1);
    for(int i = 0; i < M; ++i){
        int u = base[i].u, v = base[i].v, w = base[i].w;
        if(join(u, v)){
            adj_mst[u].eb(v, w);
            adj_mst[v].eb(u, w);
        }
    }

    dfs_mst(1, -1);
    for(int i = 0; i < K; ++i) {
        weight[i] = get_max(additional[i].u, additional[i].v);
        // cout << dbg(weight[i]) << '\n';
    }

    ll ans = 0;
    for(int mask = 1; mask < (1 << K); ++mask){
        for(int i = 0; i < K; ++i) if(mask >> i & 1){
            g[additional[i].u].pb(additional[i].v);    
            g[additional[i].v].pb(additional[i].u);    
        }  

        bool form_cycle = false;
        for(auto it : nodes){
            if(vis[it] != mask){
                form_cycle = dfs(it, -1, mask);
                if(form_cycle) break;
            }
        }

        for(auto it : nodes) g[it].clear();
        if(form_cycle) continue;

        fill(lab + 1, lab + N + 1, -1);
        for(int i = 0; i < K; ++i) if(mask >> i & 1){
            int u = additional[i].u, v = additional[i].v;
            assert(join(u, v));
            adj[u].pb(mp(i, -1));
            adj[v].pb(mp(i, -1));
        }

        for(int i = 0; i < M; ++i){
            int u = base[i].u, v = base[i].v;
            if(join(u, v)){
                // cout << u << ' ' << v << '\n';
                adj[u].pb(mp(i, 0));
                adj[v].pb(mp(i, 0));
            }
        }

        dfs_dp(1, -1, -2);
        // cout << dbg(dp[1]) << '\n';
        maximize(ans, dp[1]);
    }
    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
#endif // LOCAL

    int T = 1;
//    cin >> T;
    FOR(i, 0, T) testcase(i);

    return 0;
}

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