Submission #889142

#	Time	Username	Problem	Language	Result	Execution time	Memory
889142		damwuan	Toll (APIO13_toll)	C++14	100 / 100	979 ms	44108 KiB

toll

#include<bits/stdc++.h>
using namespace std;
#define task "test"
#define pb push_back
#define fi first
#define se second
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=6e5+69;
const ll inf=1e18;
const ll mod=1e9+7;
const ll base = 223;
int n, m, k;
int id[maxn], Cnt;
int dd[maxn];
struct Edge
{
    int u, v, w;
    bool operator < (const Edge& o) const
    {
        return w < o.w;
    }
}e[maxn];
struct usd
{
    int par[maxn];
    void init(int x=n) {fill(par,par+1+x,-1);}
    int Find(int u)
    {
        return par[u] < 0 ? u : par[u] = Find(par[u]);
    }
    bool Union(int u, int v)
    {
        if ((u = Find(u)) == (v = Find(v))) return false;
        if (par[u] > par[v]) swap(u,v);
        par[u] += par[v];
        par[v] = u;
        return true;
    }
}dsu;
vector<pii> adj[maxn];
vector<int> used, tocheck;
int ans, res,sum[maxn], dep[maxn], up[maxn], a[maxn] , sm[maxn];
bool spe[maxn];
void dfs(int u,int pre)
{
    dep[u]=dep[pre]+1;
    up[u] = pre;
    sm[u]=sum[u];
    for (auto x: adj[u])
    {
        int v=x.fi;
        int w=x.se;
        if (v==pre) continue;
        dfs(v,u);
        sm[u]+=sm[v];
        if (w <= -inf) spe[v]=1;
    }
}
void lca(int u,int v,int w)
{
    if (dep[u] < dep[v]) swap(u,v);
    while (dep[u] > dep[v])
    {
        if (spe[u])
        {
            res+=sm[u]*w;
            spe[u]=0;
        }
        u=up[u];
    }
    while (u!=v)
    {
        if (spe[u])
        {
            res+=sm[u]*w;
            spe[u]=0;
        }
        if (spe[v])
        {
            res+=sm[v]*w;
            spe[v]=0;
        }
        u=up[u];
        v=up[v];
    }
}
int cal(int mask)
{
    res=0;
    tocheck.clear();
    for (int i = 1; i <= Cnt;i++)
    {
        adj[i].clear();
        spe[i]=0;
        dep[i]=0;
    }
    dsu.init(Cnt);
    for (int i=1;i<=k;i++)
    {
        if ((mask>>(i-1))&1)
        {
            if (dsu.Union(e[i].u,e[i].v))
            {
                adj[e[i].u].pb({e[i].v, -inf});
                adj[e[i].v].pb({e[i].u, -inf});
            }
            else return 0;
        }
    }
    for (int i: used)
    {
        int u=e[i].u;
        int v=e[i].v;
        int w=e[i].w;
        if (dsu.Union(u, v))
        {
            adj[u].pb({v,w});
            adj[v].pb({u,w});
        }
        else tocheck.pb(i);
    }
    dfs(1,1);
    for (int i: tocheck) lca(e[i].u, e[i].v, e[i].w);
    return res;
}
void sol()
{
    cin >> n >> m >> k;
    for (int i = 1;i <= m ;i++)
    {
        cin >> e[i].u >> e[i].v >> e[i].w;
    }
    for (int i = m+1;i <= m+k;i++)
    {
        cin >> e[i].u >> e[i].v;
        e[i].w=-inf;
    }
    for (int i = 1;i <= n; i++)
    {
        cin >> a[i];
    }
    sort(e + 1, e + 1 + m + k);
    dsu.init();
    for (int i = 1; i <= k ; i++)
    {
        dsu.Union(e[i].u, e[i].v);
    }
    for (int i = k+1; i <= m+k; i++)
    {
        if (dsu.Union(e[i].u,e[i].v))
        {
            used.pb(i);
        }
    }
    dsu.init();
    for (int i: used) dsu.Union(e[i].u, e[i].v);
    for (int i = 1;i <= n ;i++)
    {
        int x = dsu.Find(i);
        if (!dd[x]) dd[x]=++Cnt;
        id[i] = dd[x];
        sum[dd[x]]+=a[i];
    }
    for (int i = 1;i <= m+k; i++)
    {
        e[i].u = id[e[i].u];
        e[i].v = id[e[i].v];
    }
    used.clear();
    dsu.init(Cnt);
//    for (int i = 1 ;i <= k; i++)
//    {
//        Union(e[i].u,e[i].v);
//    }
    for (int i = k + 1 ;i <= k+m; i++)
    {
        if(dsu.Union(e[i].u, e[i].v))
        {
            used.pb(i);
        }
    }
    for (int mask = 1; mask < (1<<k) ; mask++)
    {
        ans= max(ans,cal(mask));
    }
    cout << ans;
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    int t=1;//cin >> t;
    while (t--)
    {
        sol();
    }
}
/*
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 'int32_t main()':
toll.cpp:203:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  203 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:204:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  204 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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