Submission #159482

#	Time	Username	Problem	Language	Result	Execution time	Memory
159482		combi1k1	Toll (APIO13_toll)	C++14	100 / 100	2009 ms	21864 KiB

toll

#include<bits/stdc++.h>

using namespace std;

#define X   first
#define Y   second
#define pb  push_back
#define ll  long long
#define ed  tuple<int,int,int>

#define FOR(i,a,b)  for(int i = a ; i < b ; ++i)

const int   N   = 1e5 + 5;

namespace   DSU {
    int p[N];
    int s[N];
    int init(int n) {
        iota(p + 1,p + 1 + n,1);
        fill(s + 1,s + 1 + n,1);
        return  1;
    }
    int lead(int x) {
        return p[x] == x ? x : p[x] = lead(p[x]);
    }
    int join(int x,int y)   {
        x = lead(x);
        y = lead(y);
        if (x == y) return  0;
        if (s[x] < s[y])
            swap(x,y);
        p[y] = x;
        s[x] += s[y];
        return  1;
    }
};

typedef pair<int,int>   ii;

vector<ii>  g1[N];
vector<ii>  g2[N];
vector<ed>  rem;

int x[N], y[N];
ll  a[N], f[N];
int dep[N];
int idx[N], tot = 0;
ll  nCh[N], ans = 0;
ii  anc[N];
int lim[N];

int ini(int u,int p)    {
    idx[u] = tot;
    f[tot] += a[u];
    for(ii  e : g1[u])  if (e.X != p)
        ini(e.X,u);
}
int dfs(int u,int p)    {
    nCh[u] = f[u];
    for(ii  e : g2[u])  {
        if (e.X == p)   anc[u] = e;
        else
            dep[e.X] = dep[u] + 1,
            dfs(e.X,u),
            nCh[u] += nCh[e.X];
    }
}

void goUp(int &u,int w) {
    if (anc[u].Y)   lim[anc[u].Y] = min(lim[anc[u].Y],w);
    u = anc[u].X;
}

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

    int n;  cin >> n;
    int m;  cin >> m;
    int k;  cin >> k;

    vector<ed>  E;

    FOR(i,0,m)  {
        int u;  cin >> u;
        int v;  cin >> v;
        int w;  cin >> w;
        E.pb(make_tuple(w,u,v));
    }

    sort(E.begin(),E.end());    DSU::init(n);

    FOR(i,0,m)  {
        int w, u, v;
        tie(w, u, v) = E[i];
        if (DSU::join(u,v))
            E.pb(E[i]);
    }
    reverse(E.begin(),E.end()); E.resize(n - 1);
    reverse(E.begin(),E.end()); DSU::init(n);

    FOR(i,0,k)  {
        cin >> x[i] >> y[i];
        DSU::join(x[i],y[i]);
    }
    FOR(i,1,n)  {
        int w, u, v;
        tie(w, u, v) = E[i - 1];
        if (DSU::join(u,v))
            g1[u].pb({v,w}),
            g1[v].pb({u,w});
        else    rem.pb(E[i - 1]);
    }
    FOR(i,0,n)  cin >> a[i + 1];
    FOR(i,1,n + 1)  if(!idx[i]) {
        tot++;
        ini(i,0);
    }

    FOR(m,0,1 << k) {
        FOR(i,1,tot + 1)
            DSU::p[i] = i,
            DSU::s[i] = 1,
            g2[i].clear(),
            lim[i] = 1e9;

        int Cyc = 0;
        ll  res = 0;

        FOR(i,0,k)  if (m >> i & 1) {
            int u = idx[x[i]];
            int v = idx[y[i]];
            if (DSU::join(u,v))
                g2[u].pb({v,i + 1}),
                g2[v].pb({u,i + 1});
            else    Cyc = 1;
        }
        if (Cyc)    continue;

        vector<ed>  tmp;

        for(ed  e : rem)    {
            int w, u, v;
            tie(w, u, v) = e;
            u = idx[u];
            v = idx[v];
            if (DSU::join(u,v))
                g2[u].pb({v,0}),
                g2[v].pb({u,0});
            else    tmp.pb(e);
        }
        dfs(1,0);

        for(ed  e : tmp)    {
            int w, u, v;
            tie(w, u, v) = e;
            u = idx[u];
            v = idx[v];
            if (dep[u] < dep[v])
                swap(u,v);
            while (dep[u] > dep[v])
                goUp(u,w);
            while (u != v)
                goUp(u,w),
                goUp(v,w);
        }
        FOR(i,0,k)  if (m >> i & 1) {
            int u = idx[x[i]];
            int v = idx[y[i]];
            if (dep[u] > dep[v])
                swap(u,v);
            res += nCh[v] * lim[i + 1];
        }
        ans = max(ans,res);
    }

    cout << ans << endl;
}
/*
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
*/

Compilation message (stderr)

toll.cpp: In function 'int ini(int, int)':
toll.cpp:57:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
toll.cpp: In function 'int dfs(int, int)':
toll.cpp:67:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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