oj.uz

Submission #889143

# Submission time Handle Problem Language Result Execution time Memory
889143 2023-12-19T03:09:40 Z vjudge1 Toll (APIO13_toll) C++17
100 / 100
 1006 ms 40400 KB 
#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

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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 5 ms 29020 KB Output is correct
4 Correct 5 ms 29020 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 5 ms 29020 KB Output is correct
4 Correct 5 ms 29020 KB Output is correct
5 Correct 7 ms 29016 KB Output is correct
6 Correct 6 ms 29020 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 5 ms 29020 KB Output is correct
4 Correct 5 ms 29020 KB Output is correct
5 Correct 7 ms 29016 KB Output is correct
6 Correct 6 ms 29020 KB Output is correct
7 Correct 108 ms 40400 KB Output is correct
8 Correct 117 ms 40300 KB Output is correct
9 Correct 113 ms 40400 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 5 ms 29020 KB Output is correct
3 Correct 5 ms 29020 KB Output is correct
4 Correct 5 ms 29020 KB Output is correct
5 Correct 7 ms 29016 KB Output is correct
6 Correct 6 ms 29020 KB Output is correct
7 Correct 108 ms 40400 KB Output is correct
8 Correct 117 ms 40300 KB Output is correct
9 Correct 113 ms 40400 KB Output is correct
10 Correct 750 ms 40400 KB Output is correct
11 Correct 961 ms 40292 KB Output is correct
12 Correct 1006 ms 40400 KB Output is correct