oj.uz

Submission #610550

# Submission time Handle Problem Language Result Execution time Memory
610550 2022-07-28T09:58:05 Z dooompy Training (IOI07_training) C++17
72 / 100
 300 ms 2396 KB 
#include <bits/stdc++.h>

using namespace std;

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

vector<edge> edges, fe;
int total = 0;
vector<int> adj[1005];

int tin[1005], timer = 1;
int jmp[1005][12], depth[1005];
int col[1005];
pair<int, int> par[1005];
int deg[1005];
int dp[1005][1 << 11];

void dfs(int node) {
    tin[node] = timer++;

    for (int i = 1; i < 12; i++) jmp[node][i] = jmp[jmp[node][i-1]][i-i];

    for (auto nxt : adj[node]) {
        if (tin[nxt]) continue;
        if (col[node] == 1) {
            col[nxt] = 2;
        } else col[nxt] = 1;
        par[nxt] = {node, (1 << deg[node]++)};
        depth[nxt] = depth[node] + 1;
        jmp[nxt][0] = node;
        dfs(nxt);
    }
}

int lca(int a, int b) {
    if (depth[a] > depth[b]) swap(a, b);

    for (int i = 11; i >= 0; i--) {
        if (depth[jmp[b][i]] >= depth[a]) b = jmp[b][i];
    }

    if (a == b) return a;

    for (int i = 11; i >= 0; i--) {
        if (jmp[a][i] != jmp[b][i]) {
            a = jmp[a][i]; b = jmp[b][i];
        }
    }

    return jmp[a][0];
}

int main() {
    int n, m; cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        total += c;
        if (c == 0) {
            adj[a].push_back(b); adj[b].push_back(a);
        }

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

    col[1] = 1;
    jmp[1][0] = 1;
    depth[1] = 1;

    dfs(1);

    for (auto e: edges) {
        if (col[e.a] == col[e.b]) fe.push_back({e.a, e.b, e.c, lca(e.a, e.b)});
        else if (e.c == 0) fe.push_back({e.a, e.b, e.c, lca(e.a, e.b)});
    }

    sort(fe.begin(), fe.end(), [&](edge a, edge b) {
        return tin[a.lca] > tin[b.lca];
    });

    for (auto e : fe) {
        int tot = e.c;
        int finalmask = 0;
        int mask = 0;
        for (int i = e.a; i != e.lca; mask = par[i].second, i = par[i].first) {
            tot += dp[i][mask];
        }
        finalmask |= mask;
        mask = 0;
        for (int i = e.b; i != e.lca;mask = par[i].second, i = par[i].first) {
            tot += dp[i][mask];
        }
        finalmask |= mask;

        for (int mk = (1 << deg[e.lca]) - 1; mk >= 0 ; mk--) {
            if (mk & finalmask) continue;
            dp[e.lca][mk] = max(dp[e.lca][mk], dp[e.lca][mk | finalmask] + tot);
        }

    }
    cout << total - dp[1][0];
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 2396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 328 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 456 KB Output is correct
2 Correct 1 ms 468 KB Output is correct

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

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

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2260 KB Output is correct
2 Correct 7 ms 1216 KB Output is correct
3 Correct 7 ms 1620 KB Output is correct

Subtask #10
0 / 9.0

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

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 2260 KB Output isn't correct
2 Halted 0 ms 0 KB -