oj.uz

답안 #755591

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
755591 2023-06-10T11:43:10 Z onepunchac168 통행료 (APIO13_toll) C++14
100 / 100
 1502 ms 8540 KB 
// 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,Ofast")
#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 readbit(x,i) ((x>>i)&1)
#define ins insert

typedef int ll;
typedef pair <ll,bool> 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(int 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];
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];

    }
}
bool ok[M];
long long solve(int MASK)
{
    ans=0;
    for (auto v:tmp)
    {
        dsu.makeseta(v);
        vt[v].clear();
        cost[v]=1e9+5;
    }
    for (int i=1;i<=k;i++)
    {
        if (readbit(MASK,i-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 -1;
            }
            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);
            ok[v]=1;
        }
    }
    sz[mau[1]]=0;
    dfs(mau[1],-1);
    for (auto v:need)
    {
        if (ok[v]==1)
        {
            ok[v]=0;
            continue;
        }
        ll aa=mau[edges[v].a];
        ll bb=mau[edges[v].b];
        solve1(aa,bb,edges[v].c);
    }
    dfssolve(mau[1],-1);
    return ans;
}
void optmushnpr()
{
    cin>>n>>m>>k;
    for (int i=1;i<=m;i++)
    {
        cin>>edges[i].a>>edges[i].b>>edges[i].c;
    }
    for (int i=1;i<=k;i++)
    {
        cin>>edgesa[i].a>>edgesa[i].b;
    }
    for (int i=1;i<=n;i++)
    {
        cin>>cnt[i];
    }
    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);
        }
    }
    long long res=0;
    for (int i=mask(k-min(k,2));i<mask(k);i++)
    {
        res=max(res,solve(i));
    }
    cout<<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

toll.cpp: In function 'long long int solve(int)':
toll.cpp:176:27: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  176 |         if (readbit(MASK,i-1)==1)
      |                          ~^~
toll.cpp:24:27: note: in definition of macro 'readbit'
   24 | #define readbit(x,i) ((x>>i)&1)
      |                           ^
toll.cpp: In function 'int main()':
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".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:308:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  308 |     freopen(task".out","w",stdout);}
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 4 ms 2772 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 4 ms 2772 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 158 ms 8188 KB Output is correct
8 Correct 158 ms 8272 KB Output is correct
9 Correct 189 ms 8300 KB Output is correct

Subtask #5
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 4 ms 2772 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 158 ms 8188 KB Output is correct
8 Correct 158 ms 8272 KB Output is correct
9 Correct 189 ms 8300 KB Output is correct
10 Correct 1133 ms 8540 KB Output is correct
11 Correct 1486 ms 8480 KB Output is correct
12 Correct 1502 ms 8404 KB Output is correct