oj.uz

Submission #589836

# Submission time Handle Problem Language Result Execution time Memory
589836 2022-07-05T10:49:59 Z tranxuanbach Training (IOI07_training) C++17
100 / 100
 22 ms 4692 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

const int N = 1e3 + 5, M = 5e3 + 5;

struct edge_t{
    int u, v, w, t;
    int tu, tv, dp = 0;

    edge_t(){

    }

    edge_t(int u, int v, int w): u(u), v(v), w(w){

    }
};

int n, m;
vi adj[N];
vector <edge_t> a;

int h[N], par[N], idpar[N];

void dfs_par(int u){
    Fora(v, adj[u]){
        if (v == par[u]){
            continue;
        }
        par[v] = u;
        h[v] = h[u] + 1;
        dfs_par(v);
    }
    for (auto itr = adj[u].begin(); itr != adj[u].end(); itr++){
        if (*itr == par[u]){
            adj[u].erase(itr);
            break;
        }
    }
    For(i, 0, isz(adj[u])){
        idpar[adj[u][i]] = i;
    }
}

int lca(int u, int v){
    if (h[u] < h[v]){
        swap(u, v);
    }
    while (h[u] > h[v]){
        u = par[u];
    }
    while (u != v){
        u = par[u]; v = par[v];
    }
    return u;
}

int nearlca(int u, int v){
    if (h[u] < h[v]){
        swap(u, v);
    }
    while (h[u] - 1 > h[v]){
        u = par[u];
    }
    return u;
}

vector <edge_t> b[N];

int dp[N][1 << 10];

int ans;

void dfs_dp(int u){
    Fora(v, adj[u]){
        if (v == par[u]){
            continue;
        }
        dfs_dp(v);
    }

    Fora(&ed, b[u]){
        if (ed.u != u){
            ed.dp += dp[ed.u][(1 << isz(adj[ed.u])) - 1];
            int node = ed.u;
            while (node != u and par[node] != u){
                ed.dp += dp[par[node]][(1 << isz(adj[par[node]])) - 1 - (1 << idpar[node])];
                node = par[node];
            }
        }
        if (ed.v != u){
            ed.dp += dp[ed.v][(1 << isz(adj[ed.v])) - 1];
            int node = ed.v;
            while (node != u and par[node] != u){
                ed.dp += dp[par[node]][(1 << isz(adj[par[node]])) - 1 - (1 << idpar[node])];
                node = par[node];
            }
        }
    }
    int k = isz(adj[u]);
    For(msk, 0, (1 << k)){
        {
            For(i, 0, k){
                if (msk >> i & 1){
                    dp[u][msk] += dp[adj[u][i]][(1 << isz(adj[adj[u][i]])) - 1];
                }
            }
        }
        Fora(&ed, b[u]){
            if ((ed.tu == u or (msk >> idpar[ed.tu] & 1)) and (ed.tv == u or (msk >> idpar[ed.tv] & 1))){
                int tmsk = msk;
                if (ed.tu != u){
                    tmsk ^= 1 << idpar[ed.tu];
                }
                if (ed.tv != u){
                    tmsk ^= 1 << idpar[ed.tv];
                }
                dp[u][msk] = max(dp[u][msk], ed.w + dp[u][tmsk] + ed.dp);
            }
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    cin >> n >> m;
    ForE(i, 1, m){
        int u, v, w; cin >> u >> v >> w;
        if (w == 0){
            adj[u].emplace_back(v);
            adj[v].emplace_back(u);
        }
        else{
            a.emplace_back(u, v, w);
            ans += w;
        }
    }
    m -= n - 1;

    dfs_par(1);

    Fora(&ed, a){
        if ((h[ed.u] + h[ed.v]) & 1){
            continue;
        }
        int t = lca(ed.u, ed.v);
        ed.tu = nearlca(ed.u, t);
        ed.tv = nearlca(ed.v, t);
        b[t].emplace_back(ed);
    }

    dfs_dp(1);

    ans -= dp[1][(1 << isz(adj[1])) - 1];
    cout << ans << endl;
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 0 ms 596 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 724 KB Output is correct

Subtask #8
9.0 / 9.0

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

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2296 KB Output is correct
2 Correct 9 ms 1236 KB Output is correct
3 Correct 5 ms 1620 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 724 KB Output is correct
2 Correct 3 ms 1588 KB Output is correct
3 Correct 22 ms 4692 KB Output is correct
4 Correct 4 ms 1748 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2152 KB Output is correct
2 Correct 17 ms 4596 KB Output is correct
3 Correct 8 ms 1748 KB Output is correct
4 Correct 10 ms 1512 KB Output is correct