Submission #762167

#	Time	Username	Problem	Language	Result	Execution time	Memory
762167		onepunchac168	Toll (APIO13_toll)	C++14	100 / 100	939 ms	8360 KiB

toll

// created by Dinh Manh Hung
// tht.onepunchac168
// THPT CHUYEN HA TINH
// HA TINH, VIET NAM

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

//#pragma GCC optimize("O3,unroll-loops,no-stack-protector")
//#pragma GCC target("sse4,avx2,fma")
#define task ""
#define ldb long double
#define pb emplace_back
#define fi first
#define se second
#define pc pop_back()
#define all(x) begin(x),end(x)
#define uniquev(v) v.resize(unique(all(v))-v.begin())
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define cntbit(v) __builtin_popcountll(v)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) ((1LL*a*b)/__gcd(a,b))
#define mask(x) (1LL<<(x))
#define ins insert

typedef int ll;
typedef pair <ll,ll> ii;
typedef pair <ll,ii> iii;
typedef pair <ii,ii> iiii;

ll dx[]= {1,-1,0,0,1,-1,1,-1};
ll dy[]= {0,0,-1,1,1,-1,-1,1};

const ldb PI = acos (-1);
//const ll mod=978846151;
//const ll base=29;
const int maxn=1e6+5;
const int mod=1e9+7;
const char nl = '\n';
inline int ReadInt()
{
    char co;
    for (co = getchar(); co < '0' || co > '9'; co = getchar());
    int xo = co - '0';
    for (co = getchar(); co >= '0' && co <= '9'; co = getchar())
        xo = xo * 10 + co - '0';
    return xo;
}

void WriteInt(long long xo)
{
    if (xo > 9)
        WriteInt(xo / 10);
    putchar(xo % 10 + '0');
}
/* END OF TEMPLATE*/

// ================= Solution =================//

ll n,m,k;
const int N=1e5+5;
const int M=3e5+5;
bool check1[M];
bool check2[M];
struct pt{
    ll a,b,c;
}edges[M],edgesa[25];
ll cnt[N];
long long dem[N];
int cost[N];
ll mau[N];
vector <ll> need,tmp;
vector <ii> vt[N];
long long res=0;
struct DSU{
    ll lab[N];
    void makeset()
    {
        for (int i=1;i<=n;i++)
        {
            lab[i]=-1;
        }
    }
    void makeseta(int u)
    {
        lab[u]=-1;
    }
    ll findset(int u)
    {
        if (lab[u]<0)
        {
            return u;
        }
        return lab[u]=findset(lab[u]);
    }
    void Union(int r,int s)
    {
        if (lab[r]>lab[s])
        {
            swap(r,s);
        }
        lab[r]+=lab[s];
        lab[s]=r;
    }
} dsu;
bool cmp(pt u,pt v)
{
    return u.c<v.c;
}
ll sz[N];
ll cha[N];
long long dd[N];
void dfs(int u,int vv)
{
    for (auto v:vt[u])
    {
        if (v.fi==vv)
        {
            continue;
        }
        cha[v.fi]=u;
        sz[v.fi]=sz[u]+1;
        dfs(v.fi,u);
    }
}
void solve1(int u,int v,ll w)
{
    if (sz[u]>sz[v])
    {
        swap(u,v);
    }
    while (sz[u]<sz[v])
    {
        cost[v]=min(cost[v],w);
        v=cha[v];
    }
    while (u!=v)
    {
        cost[u]=min(cost[u],w);
        cost[v]=min(cost[v],w);
        u=cha[u];
        v=cha[v];
    }
}
long long ans;
void dfssolve(int u,int vv)
{
    dd[u]=dem[u];
    for (auto v:vt[u])
    {
        if (v.fi==vv)
        {
            continue;
        }
        dfssolve(v.fi,u);
        if (v.se==1)
        {
            ans+=cost[v.fi]*dd[v.fi];
        }
        dd[u]+=dd[v.fi];
    }
}
vector <ll> opt;
void solve(int MASK)
{
    ans=0;
    opt.clear();
    for (auto v:tmp)
    {
        dsu.makeseta(v);
        vt[v].clear();
        cost[v]=1e9+5;
    }
    for (int i=1;i<=k;i++)
    {
        if ((MASK>>(i-1)&1)==1)
        {
            ll aa=mau[edgesa[i].a];
            ll bb=mau[edgesa[i].b];
            ll a1=dsu.findset(aa);
            ll a2=dsu.findset(bb);
            if (a1==a2)
            {
                return;
            }
            vt[aa].pb(bb,1);
            vt[bb].pb(aa,1);
            dsu.Union(a1,a2);
        }
    }
    for (auto v:need)
    {
        ll aa=mau[edges[v].a];
        ll bb=mau[edges[v].b];
        ll a1=dsu.findset(aa);
        ll a2=dsu.findset(bb);
        if (a1!=a2)
        {
            vt[aa].pb(bb,0);
            vt[bb].pb(aa,0);
            dsu.Union(a1,a2);
        }
        else opt.pb(v);
    }
    sz[mau[1]]=0;
    dfs(mau[1],-1);
    for (auto v:opt)
    {
        ll aa=mau[edges[v].a];
        ll bb=mau[edges[v].b];
        solve1(aa,bb,edges[v].c);
    }
    dfssolve(mau[1],-1);
    res=max(res,ans);
}
void optmushnpr()
{
    n=ReadInt();
    m=ReadInt();
    k=ReadInt();
    for (int i=1;i<=m;i++)
    {
        edges[i].a=ReadInt();
        edges[i].b=ReadInt();
        edges[i].c=ReadInt();;
    }
    for (int i=1;i<=k;i++)
    {
        edgesa[i].a=ReadInt();
        edgesa[i].b=ReadInt();
    }
    for (int i=1;i<=n;i++)
    {
        cnt[i]=ReadInt();
    }
    dsu.makeset();
    sort (edges+1,edges+m+1,cmp);
    for (int i=1;i<=m;i++)
    {
        ll aa=dsu.findset(edges[i].a);
        ll bb=dsu.findset(edges[i].b);
        if (aa!=bb)
        {
            check1[i]=true;
            dsu.Union(aa,bb);
        }
    }
    dsu.makeset();
    for (int i=1;i<=k;i++)
    {
        ll aa=dsu.findset(edgesa[i].a);
        ll bb=dsu.findset(edgesa[i].b);
        if (aa!=bb)
        {
            dsu.Union(aa,bb);
        }
    }
    for (int i=1;i<=m;i++)
    {
        ll aa=dsu.findset(edges[i].a);
        ll bb=dsu.findset(edges[i].b);
        if (aa!=bb)
        {
            check2[i]=true;
            dsu.Union(aa,bb);
        }
    }
    dsu.makeset();
    for (int i=1;i<=m;i++)
    {
        if (check1[i]==true)
        {
            if (check2[i]==true)
            {
                dsu.Union(dsu.findset(edges[i].a),dsu.findset(edges[i].b));
            }
            else
            {
                need.pb(i);
            }
        }
    }
    for (int i=1;i<=n;i++)
    {
        ll aa=dsu.findset(i);
        mau[i]=aa;
        dem[aa]+=cnt[i];
        if (aa==i)
        {
            tmp.pb(i);
        }
    }
    for (int i=mask(k-min(k,2));i<mask(k);i++)
    {
        solve(i);
    }
    WriteInt(res);

}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen(task".inp","r")){
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);}
    int tests;
    tests=1;
    //cin>>tests;
    while (tests--){optmushnpr();}
}

// goodbye see ya

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:306:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  306 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:307:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  307 |     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