oj.uz

Submission #624910

# Submission time Handle Problem Language Result Execution time Memory
624910 2022-08-09T02:56:51 Z Huy Toll (APIO13_toll) C++17
16 / 100
 69 ms 468 KB 
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,ll>
#define fi first
#define se second
/*#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")*/
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ldb = long double;
const ll N = (int)1e9 + 1;
const int maxN = (int)1e6 + 5;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const ll infty = 1e18 + 7;
const int base = (int)4e5;
const int Block_size = 350;

void InputFile()
{
    //freopen("scrivener.inp","r",stdin);
    //freopen("scrivener.out","w",stdout);
    //freopen("test.out","r",stdin);
}

void FastInput()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

struct TEdge
{
    int x,y,w;
};

int n,m,k;
vector<vector<pii>> adj;
int a[maxN],b[maxN],c[maxN];
int x[maxN],y[maxN];
int p[maxN];
int id[maxN];
int wk[maxN];
vector<int> edg_list;

int lab[maxN];

int Findset(int u)
{
    if(lab[u] < 0) return u;
    return lab[u] = Findset(lab[u]);
}

void Unite(int r,int s)
{
    if(lab[r] > lab[s]) swap(r,s);
    lab[r] += lab[s];
    lab[s] = r;
}

void Read()
{
    cin >> n >> m >> k;
    adj.resize(n+1);
    for(int i = 1;i <= m;i++)
    {
        cin >> a[i] >> b[i] >> c[i];
        id[i] = i;
    }
    for(int i = 1;i <= k;i++)
    {
        cin >> x[i] >> y[i];
    }
    for(int i = 1;i <= n;i++)
    {
        cin >> p[i];
    }
}

bool FA(int i,int j)
{
    return c[i] < c[j];
}

void Find_MST()
{
    sort(id + 1,id + m + 1,FA);
    fill(lab + 1,lab + n + 1,-1);
    for(int i = 1;i <= m;i++)
    {
        int r = Findset(a[id[i]]);
        int s = Findset(b[id[i]]);
        if(r != s)
        {
            Unite(r,s);
            adj[a[id[i]]].push_back({b[id[i]],c[id[i]]});
            adj[b[id[i]]].push_back({a[id[i]],c[id[i]]});
        }
    }
}

int anc[20][maxN];
int f[20][maxN];
int depth[maxN];

void DFS(int u,int p)
{
    for(pii e : adj[u])
    {
        int v = e.fi;
        int w = e.se;
        if(v == p) continue;
        depth[v] = depth[u] + 1;
        anc[0][v] = u;
        f[0][v] = w;
        for(int i = 1;i <= log2(n);i++)
        {
            anc[i][v] = anc[i-1][anc[i-1][v]];
            f[i][v] = max(f[i-1][v],f[i-1][anc[i-1][v]]);
            DFS(v,u);
        }
    }
}

int Get(int u,int v)
{
    if(depth[u] < depth[v]) swap(u,v);
    int k = depth[u] - depth[v];
    int res = 0;
    for(int i = log2(n);i >= 0;i--)
    {
        if(k & (1 << i))
        {
            res = max(res,f[i][u]);
            u = anc[i][u];
        }
    }
    if(u == v) return res;
    for(int i = log2(n);i >= 0;i--)
    {
        if(anc[i][u] != anc[i][v])
        {
            res = max(res,f[i][u]);
            res = max(res,f[i][v]);
            u = anc[i][u];
            v = anc[i][v];
        }
    }
    res = max(res,f[0][u]);
    res = max(res,f[0][v]);
    return res;
}

ll val = 0;
int len = 0;
void DFS_Cal(int u,int par)
{
    val += p[u] * len;
    for(pii e : adj[u])
    {
        int v = e.fi;
        int w = e.se;
        if(v == par) continue;
        len += w;
        DFS_Cal(v,u);
        len -= w;
    }
}

void Solve()
{
    //cout <<"dark";return;
    Find_MST();
    DFS(1,0);
    for(int i = 1;i <= k;i++)
    {
        wk[i] = Get(x[i],y[i]);
    }
    //cout << wk[1];return;
    ll res = 0;
    for(int mask = 0;mask < (1 << k);mask++)
    {
        adj.clear();
        adj.resize(n+1);
        fill(lab + 1,lab + n + 1,-1);
        for(int i = 1;i <= k;i++)
        {
            if(mask & (1 << (i-1)))
            {
                int r = Findset(x[i]);
                int s = Findset(y[i]);
                if(r != s)
                {
                    Unite(r,s);
                    adj[x[i]].push_back({y[i],wk[i]});
                    adj[y[i]].push_back({x[i],wk[i]});
                }
            }
        }
        for(int i = 1;i <= m;i++)
        {
            int r = Findset(a[id[i]]);
            int s = Findset(b[id[i]]);
            if(r != s)
            {
               Unite(r,s);
               adj[a[id[i]]].push_back({b[id[i]],0});
               adj[b[id[i]]].push_back({a[id[i]],0});
            }
        }
        val = 0;
        len = 0;
        DFS_Cal(1,0);
        res = max(res,val);
    }
    cout << res;
}

void Debug()
{

}


int32_t main()
{
    FastInput();
    //InputFile();
    //int sub_type;
    //cin >> sub_type;
    //Sieve();
    //Prepare();
    int test;
    //cin >> test;
    test = 1;
    while(test--)
    {
        Read();
        Solve();
        //Debug();
    }
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Incorrect 69 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Incorrect 69 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Incorrect 69 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Incorrect 69 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -