Submission #1206607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206607		nrg_studio	통행료 (APIO13_toll)	C++20	100 / 100	1687 ms	14780 KiB

toll

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

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define vec vector

const int MAX_N = 1e5, MAX_M = 3e5, MAX_K = 21;

struct DSU {
    vec<int> par, sz;
    int n;
    DSU(int n1) {
        n = n1;
        sz = vec<int>(n,1);
        par = vec<int>(n);
        iota(all(par),0);
    }
    int get(int x) {return (par[x]==x ? x : par[x]=get(par[x]));} 
    bool merge(int a, int b) {
        a = get(a); b = get(b);
        if (a==b) {return false;}
        if (sz[a]<sz[b]) {swap(a,b);}
        par[b] = a; sz[a] += sz[b];
        return true;
    }
};
struct Edge {
    int u, v; ll w;
    Edge() {};
    Edge(int u1, int v1, ll w1) : u(u1), v(v1), w(w1) {};
    bool operator<(const Edge& o) {return w<o.w;}
};

ll new_p[MAX_K] = {0};

vec<Edge> adj[MAX_K];
DSU mst3(MAX_K);
int pa[MAX_K], dep[MAX_K];
ll psum[MAX_K] = {0}, val[MAX_K] = {0};
ll ans = 0;

void reset() {
    for (int i=0;i<MAX_K;i++) {adj[i].clear();}
    mst3.sz.assign(MAX_K,1);
    iota(all(mst3.par),0);
}
bool trymerge(int a, int b, ll c) {
    if (mst3.merge(a,b)) {
        adj[a].pb(Edge(a,b,c)); adj[b].pb(Edge(b,a,c));
        return true;
    } return false;
}

void precalc(int cur, int p, int d) {
    pa[cur] = p; psum[cur] = new_p[cur]; dep[cur] = d;
    for (Edge& x : adj[cur]) {
        if (x.v!=p) {
            precalc(x.v,cur,d+1);
            psum[cur] += psum[x.v];
            val[x.v] = x.w;
        }
    }
}
void updweight(int a, int b, ll c) {
    if (dep[a]<dep[b]) {swap(a,b);}
    while (dep[a]!=dep[b]) {
        chmin(val[a],c);
        a = pa[a];
    }
    while (a!=b) {
        chmin(val[a],c); chmin(val[b],c);
        a = pa[a]; b = pa[b];
    }
}
ll dfsans(int cur, int p) {
    ll ret = 0;
    for (Edge& x : adj[cur]) {
        if (x.v!=p) {ret += dfsans(x.v,cur);}
    } return ret+val[cur]*psum[cur];
}

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

    int n, m, k; cin >> n >> m >> k;
    Edge old_e[MAX_M];
    Edge new_e[MAX_M];
    ll p[MAX_N];

    for (int i=0;i<m;i++) {
        cin >> old_e[i].u >> old_e[i].v >> old_e[i].w;
        old_e[i].u--; old_e[i].v--;
    }
    for (int i=0;i<k;i++) {
        cin >> new_e[i].u >> new_e[i].v; new_e[i].w = LLONG_MAX;
        new_e[i].u--; new_e[i].v--;
    }
    sort(old_e,old_e+m);

    for (int i=0;i<n;i++) {cin >> p[i];}

    vec<Edge> extra, add;
    DSU mst1(n), mst2(n);
    for (int i=0;i<k;i++) {mst2.merge(new_e[i].u,new_e[i].v);}
    for (int i=0;i<m;i++) {
        bool s1 = mst1.merge(old_e[i].u,old_e[i].v);
        if (s1!=mst2.merge(old_e[i].u,old_e[i].v)) {
            extra.pb(old_e[i]);
        } else if (s1) {
            add.pb(old_e[i]);
        }
    }

    mst1 = DSU(n);
    for (Edge e : add) {mst1.merge(e.u,e.v);}
    int comp[MAX_N]; memset(comp,-1,sizeof(comp));
    for (int i=0;i<n;i++) {comp[mst1.get(i)] = 1;}
    int c = 0;
    for (int i=0;i<n;i++) {
        if (comp[i]!=-1) {comp[i] = c++;}
    }
    assert(c<=MAX_K);
    for (int i=0;i<n;i++) {new_p[comp[i]=comp[mst1.get(i)]] += p[i];}
    for (Edge& e : extra) {e.u = comp[e.u]; e.v = comp[e.v];}
    for (int i=0;i<k;i++) {new_e[i].u = comp[new_e[i].u]; new_e[i].v = comp[new_e[i].v];}
    //for (int i=0;i<n;i++) {cout << comp[i]<<' ';}
    //for (Edge& e : extra) {cout << e.u+1 << ' ' << e.v+1 << '\n';}
    //return 0;

    for (int mask=0;mask<(1<<k);mask++) {  
        reset();
        for (int i=0;i<k;i++) {
            if ((1<<i)&mask) {
                trymerge(new_e[i].u,new_e[i].v,new_e[i].w);
            }
        }
        vec<Edge> cyc;
        for (int i=0;i<k;i++) {
            if (!trymerge(extra[i].u,extra[i].v,0)) {cyc.pb(extra[i]);}
        }
        
        precalc(comp[0],-1,0);
        for (Edge& e : cyc) {updweight(e.u,e.v,e.w);}
        chmax(ans,dfsans(comp[0],-1));
        
    } cout << ans << '\n';

    /*
    iterate 2^k
    edges in mst are unique
    need to maximize edge weights
    kruskal's ; cycle chmin new edges in cycle

    take base mst
    for a subset add each edge remove edge with max weight in the cycle it forms

    no matter permutation of additions, union of removals is same
    so basically, k edges removed (consider the max subset)

    to find those edges:
    i.e take the base mst, and compare it to the mst with all k edges
    so for size s, need to consider removal of only s edges in the set of k
    doesn't matter if there is a cycle of only new edges (removals are still same)
    
    derive weights of edges:
    first delete that set of removable edges so create forest

    compress trees into nodes and sum up p
    then do 
    */
}

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