oj.uz

Submission #906021

# Submission time Handle Problem Language Result Execution time Memory
906021 2024-01-13T10:02:13 Z Alcabel Training (IOI07_training) C++17
100 / 100
 11 ms 4728 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e3, maxchildren = 10;
vector<int> g[maxn], through[maxn];
int par[maxn], parIdx[maxn], h[maxn], tin[maxn], tout[maxn], tt;
vector<pair<int, int>> edges;
vector<int> w;

void dfsRoot(int v) {
    tin[v] = tt++;
    for (int i = 0; i < (int)g[v].size(); ++i) {
        int u = g[v][i];
        if (u != par[v]) {
            par[u] = v;
            parIdx[u] = i;
            h[u] = h[v] + 1;
            dfsRoot(u);
        } else {
            swap(g[v][i], g[v].back());
            g[v].pop_back();
            --i;
        }
    }
    tout[v] = tt++;
}

bool isAncestor(int v, int u) {
    return tin[v] <= tin[u] && tout[v] >= tout[u];
}

int dp[maxn][1 << maxchildren];

void dfsAns(int v) {
    for (const int& u : g[v]) {
        dfsAns(u);
    }
    int c = g[v].size();
    for (int mask = 0; mask < (1 << c); ++mask) {
        dp[v][mask] = 0;
        for (int i = 0; i < c; ++i) {
            if (mask & (1 << i)) {
                dp[v][mask] += dp[g[v][i]][(1 << g[g[v][i]].size()) - 1];
            }
        }
    }
    int m = through[v].size();
    for (int i = 0; i < m; ++i) {
        int cost = w[through[v][i]], u, sub = 0;
        u = edges[through[v][i]].first;
        if (u != v) {
            cost += dp[u][(1 << g[u].size()) - 1];
            while (par[u] != v) {
                int p = par[u];
                cost += dp[p][((1 << g[p].size()) - 1) ^ (1 << parIdx[u])];
                u = p;
            }
            sub |= (1 << parIdx[u]);
        }
        u = edges[through[v][i]].second;
        if (u != v) {
            cost += dp[u][(1 << g[u].size()) - 1];
            while (par[u] != v) {
                int p = par[u];
                cost += dp[p][((1 << g[p].size()) - 1) ^ (1 << parIdx[u])];
                u = p;
            }
            sub |= (1 << parIdx[u]);
        }
        for (int mask = (1 << c) - 1; mask >= 0; --mask) {
            if ((mask & sub) == sub) {
                dp[v][mask] = max(dp[v][mask], cost + dp[v][mask ^ sub]);
            }
        }
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    int sumAll = 0;
    for (int i = 0; i < m; ++i) {
        int v, u, weight;
        cin >> v >> u >> weight;
        --v, --u;
        if (weight == 0) {
            g[v].emplace_back(u);
            g[u].emplace_back(v);
        } else {
            sumAll += weight;
            edges.emplace_back(v, u);
            w.emplace_back(weight);
        }
    }
    par[0] = parIdx[0] = -1;
    h[0] = 0;
    tt = 0;
    dfsRoot(0);
    for (int i = 0; i < (int)edges.size(); ++i) {
        int v = edges[i].first, u = edges[i].second;
        if (h[v] % 2 != h[u] % 2) {
            swap(edges[i], edges.back());
            swap(w[i], w.back());
            edges.pop_back();
            w.pop_back();
            --i;
            continue;
        }
        if (tin[v] > tin[u]) {
            swap(edges[i].first, edges[i].second);
            swap(v, u);
        }
        int lca = v;
        while (!isAncestor(lca, u)) {
            lca = par[lca];
        }
        through[lca].emplace_back(i);
    }
    dfsAns(0);
    cout << sumAll - dp[0][(1 << g[0].size()) - 1] << '\n';
}

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

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4640 KB Output is correct
2 Correct 4 ms 4620 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 516 KB Output is correct

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2616 KB Output is correct

Subtask #8
9.0 / 9.0

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

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4624 KB Output is correct
2 Correct 5 ms 4608 KB Output is correct
3 Correct 3 ms 4700 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2652 KB Output is correct
2 Correct 3 ms 2652 KB Output is correct
3 Correct 11 ms 4728 KB Output is correct
4 Correct 2 ms 2804 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4700 KB Output is correct
2 Correct 8 ms 4700 KB Output is correct
3 Correct 6 ms 4700 KB Output is correct
4 Correct 5 ms 4448 KB Output is correct