oj.uz

답안 #889142

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
889142 2023-12-19T03:09:04 Z damwuan 통행료 (APIO13_toll) C++14
100 / 100
 979 ms 44108 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 6 ms 29208 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 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 6 ms 29208 KB Output is correct
5 Correct 7 ms 29276 KB Output is correct
6 Correct 7 ms 29316 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 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 6 ms 29208 KB Output is correct
5 Correct 7 ms 29276 KB Output is correct
6 Correct 7 ms 29316 KB Output is correct
7 Correct 113 ms 43880 KB Output is correct
8 Correct 118 ms 43920 KB Output is correct
9 Correct 114 ms 43876 KB Output is correct

Subtask #5
22.0 / 22.0

# 결과 실행 시간 메모리 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 6 ms 29208 KB Output is correct
5 Correct 7 ms 29276 KB Output is correct
6 Correct 7 ms 29316 KB Output is correct
7 Correct 113 ms 43880 KB Output is correct
8 Correct 118 ms 43920 KB Output is correct
9 Correct 114 ms 43876 KB Output is correct
10 Correct 758 ms 44108 KB Output is correct
11 Correct 973 ms 43984 KB Output is correct
12 Correct 979 ms 43984 KB Output is correct