oj.uz

Submission #170452

# Submission time Handle Problem Language Result Execution time Memory
170452 2019-12-25T10:27:54 Z dolphingarlic Training (IOI07_training) C++14
100 / 100
 16 ms 4728 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;

struct R {
    int a, b, c, lca;
};

vector<int> t[5001];
vector<R> r;
pair<int, int> p[5001];
bool e[5001];
int dp[5001][1 << 10], ti = 0, tin[5001], tout[5001], dg[5001];

bool operator<(R A, R B) {
    return tout[A.lca] < tout[B.lca];
}

void d(int u = 1, int parent = 0) {
    e[u] = !e[parent];
    tin[u] = ++ti;
    for (int i : t[u]) {
        if (i != parent) {
            p[i] = {u, 1 << dg[u]++};
            d(i, u);
        }
    }
    tout[u] = ++ti;
}

bool par(int A, int B) {
    return tin[A] <= tin[B] && tout[A] >= tout[B];
}
int lca(int A, int B) {
    while (!par(A, B)) A = p[A].first;
    return A;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, cost = 0;
    cin >> n >> m;
    FOR(i, 0, m) {
        int a, b, c;
        cin >> a >> b >> c;
        cost += c;
        if (!c) {
            t[a].push_back(b);
            t[b].push_back(a);
        }

        r.push_back({a, b, c});
    }

    d();

    FOR(i, 0, m) r[i].lca = lca(r[i].a, r[i].b);
    sort(r.begin(), r.end());

    for (R i : r) {
        if (i.c && e[i.a] ^ e[i.b]) continue;

        int sm = i.c;
        pair<int, int> A, B;
        for (A = {i.a, 0}; A.first != i.lca; A = p[A.first]) sm += dp[A.first][A.second];
        for (B = {i.b, 0}; B.first != i.lca; B = p[B.first]) sm += dp[B.first][B.second];

        for (int mask = (1 << dg[i.lca]) - 1; ~mask; mask--) {
            if (!(mask & A.second || mask & B.second)) {
                dp[i.lca][mask] = max(dp[i.lca][mask], sm + dp[i.lca][mask | A.second | B.second]);
            }
        }
    }

    cout << cost - dp[1][0];
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4728 KB Output is correct
2 Correct 10 ms 4728 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1144 KB Output is correct
2 Correct 4 ms 1148 KB Output is correct
3 Correct 6 ms 1700 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2396 KB Output is correct
2 Correct 8 ms 1288 KB Output is correct
3 Correct 6 ms 1656 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 5 ms 1784 KB Output is correct
3 Correct 16 ms 4600 KB Output is correct
4 Correct 6 ms 1912 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2216 KB Output is correct
2 Correct 15 ms 4728 KB Output is correct
3 Correct 9 ms 1784 KB Output is correct
4 Correct 8 ms 1528 KB Output is correct