oj.uz

Submission #545967

# Submission time Handle Problem Language Result Execution time Memory
545967 2022-04-05T18:05:47 Z stefantaga Training (IOI07_training) C++14
100 / 100
 17 ms 4544 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int mx = 1005;

int n, m, ans, dep[mx], tin[mx], tout[mx], cnt, par[mx], pos[mx], deg[mx], dp[mx][(1<<10)];
vector<int> adj[mx]; vector<edge> pth;

void dfs(int i){
    tin[i] = cnt++;
    for (int x : adj[i])
        if (x != par[i])
            dep[x] = dep[i]+1, par[x] = i, pos[x] = (1<<deg[i]++), dfs(x);
    tout[i] = cnt-1;
}int LCA(int a, int b){
    while (!(tin[a] <= tin[b] and tout[b] <= tout[a])) a = par[a];
    return a;
}

int main(){
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int a, b, w; cin >> a >> b >> w; ans += w;
        if (!w) adj[a].push_back(b), adj[b].push_back(a);
        pth.push_back({a, b, w});
    }dfs(1); for (auto &r : pth) r.lca = LCA(r.a, r.b);
    sort(pth.begin(), pth.end(), [](edge x, edge y){ return tin[x.lca] > tin[y.lca]; });
    for (auto r : pth) if (!(r.w and (dep[r.a]+dep[r.b])%2)){
        int sum = r.w, p1 = 0, p2 = 0;
        for (int x = r.a; x != r.lca; p1 = pos[x], x = par[x]) sum += dp[x][p1];
        for (int x = r.b; x != r.lca; p2 = pos[x], x = par[x]) sum += dp[x][p2];
        for (int msk = 0; msk < (1<<deg[r.lca]); msk++)
            if (!(msk&p1) and !(msk&p2))
                dp[r.lca][msk] = max(dp[r.lca][msk], dp[r.lca][(msk|p1|p2)]+sum);
    }cout<<ans-dp[1][0]<<endl;
}

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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4516 KB Output is correct
2 Correct 8 ms 4500 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 332 KB Output is correct

Subtask #5
9.0 / 9.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 #6
9.0 / 9.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 #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

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

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2132 KB Output is correct
2 Correct 6 ms 1108 KB Output is correct
3 Correct 5 ms 1440 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 4 ms 1620 KB Output is correct
3 Correct 17 ms 4436 KB Output is correct
4 Correct 5 ms 1656 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2004 KB Output is correct
2 Correct 16 ms 4544 KB Output is correct
3 Correct 8 ms 1620 KB Output is correct
4 Correct 6 ms 1320 KB Output is correct