oj.uz

Submission #159482

# Submission time Handle Problem Language Result Execution time Memory
159482 2019-10-22T23:35:23 Z combi1k1 Toll (APIO13_toll) C++14
100 / 100
 2009 ms 21864 KB 
#include<bits/stdc++.h>

using namespace std;

#define X   first
#define Y   second
#define pb  push_back
#define ll  long long
#define ed  tuple<int,int,int>

#define FOR(i,a,b)  for(int i = a ; i < b ; ++i)

const int   N   = 1e5 + 5;

namespace   DSU {
    int p[N];
    int s[N];
    int init(int n) {
        iota(p + 1,p + 1 + n,1);
        fill(s + 1,s + 1 + n,1);
        return  1;
    }
    int lead(int x) {
        return p[x] == x ? x : p[x] = lead(p[x]);
    }
    int join(int x,int y)   {
        x = lead(x);
        y = lead(y);
        if (x == y) return  0;
        if (s[x] < s[y])
            swap(x,y);
        p[y] = x;
        s[x] += s[y];
        return  1;
    }
};

typedef pair<int,int>   ii;

vector<ii>  g1[N];
vector<ii>  g2[N];
vector<ed>  rem;

int x[N], y[N];
ll  a[N], f[N];
int dep[N];
int idx[N], tot = 0;
ll  nCh[N], ans = 0;
ii  anc[N];
int lim[N];

int ini(int u,int p)    {
    idx[u] = tot;
    f[tot] += a[u];
    for(ii  e : g1[u])  if (e.X != p)
        ini(e.X,u);
}
int dfs(int u,int p)    {
    nCh[u] = f[u];
    for(ii  e : g2[u])  {
        if (e.X == p)   anc[u] = e;
        else
            dep[e.X] = dep[u] + 1,
            dfs(e.X,u),
            nCh[u] += nCh[e.X];
    }
}

void goUp(int &u,int w) {
    if (anc[u].Y)   lim[anc[u].Y] = min(lim[anc[u].Y],w);
    u = anc[u].X;
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int m;  cin >> m;
    int k;  cin >> k;

    vector<ed>  E;

    FOR(i,0,m)  {
        int u;  cin >> u;
        int v;  cin >> v;
        int w;  cin >> w;
        E.pb(make_tuple(w,u,v));
    }

    sort(E.begin(),E.end());    DSU::init(n);

    FOR(i,0,m)  {
        int w, u, v;
        tie(w, u, v) = E[i];
        if (DSU::join(u,v))
            E.pb(E[i]);
    }
    reverse(E.begin(),E.end()); E.resize(n - 1);
    reverse(E.begin(),E.end()); DSU::init(n);

    FOR(i,0,k)  {
        cin >> x[i] >> y[i];
        DSU::join(x[i],y[i]);
    }
    FOR(i,1,n)  {
        int w, u, v;
        tie(w, u, v) = E[i - 1];
        if (DSU::join(u,v))
            g1[u].pb({v,w}),
            g1[v].pb({u,w});
        else    rem.pb(E[i - 1]);
    }
    FOR(i,0,n)  cin >> a[i + 1];
    FOR(i,1,n + 1)  if(!idx[i]) {
        tot++;
        ini(i,0);
    }

    FOR(m,0,1 << k) {
        FOR(i,1,tot + 1)
            DSU::p[i] = i,
            DSU::s[i] = 1,
            g2[i].clear(),
            lim[i] = 1e9;

        int Cyc = 0;
        ll  res = 0;

        FOR(i,0,k)  if (m >> i & 1) {
            int u = idx[x[i]];
            int v = idx[y[i]];
            if (DSU::join(u,v))
                g2[u].pb({v,i + 1}),
                g2[v].pb({u,i + 1});
            else    Cyc = 1;
        }
        if (Cyc)    continue;

        vector<ed>  tmp;

        for(ed  e : rem)    {
            int w, u, v;
            tie(w, u, v) = e;
            u = idx[u];
            v = idx[v];
            if (DSU::join(u,v))
                g2[u].pb({v,0}),
                g2[v].pb({u,0});
            else    tmp.pb(e);
        }
        dfs(1,0);

        for(ed  e : tmp)    {
            int w, u, v;
            tie(w, u, v) = e;
            u = idx[u];
            v = idx[v];
            if (dep[u] < dep[v])
                swap(u,v);
            while (dep[u] > dep[v])
                goUp(u,w);
            while (u != v)
                goUp(u,w),
                goUp(v,w);
        }
        FOR(i,0,k)  if (m >> i & 1) {
            int u = idx[x[i]];
            int v = idx[y[i]];
            if (dep[u] > dep[v])
                swap(u,v);
            res += nCh[v] * lim[i + 1];
        }
        ans = max(ans,res);
    }

    cout << ans << endl;
}
/*
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 'int ini(int, int)':
toll.cpp:57:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
toll.cpp: In function 'int dfs(int, int)':
toll.cpp:67:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 9 ms 5368 KB Output is correct
6 Correct 9 ms 5368 KB Output is correct
7 Correct 234 ms 20600 KB Output is correct
8 Correct 243 ms 20664 KB Output is correct
9 Correct 242 ms 20568 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 9 ms 5368 KB Output is correct
6 Correct 9 ms 5368 KB Output is correct
7 Correct 234 ms 20600 KB Output is correct
8 Correct 243 ms 20664 KB Output is correct
9 Correct 242 ms 20568 KB Output is correct
10 Correct 1545 ms 20692 KB Output is correct
11 Correct 1990 ms 20644 KB Output is correct
12 Correct 2009 ms 21864 KB Output is correct