oj.uz

Submission #1041228

# Submission time Handle Problem Language Result Execution time Memory
1041228 2024-08-01T18:28:15 Z ThommyDB Training (IOI07_training) C++17
100 / 100
 10 ms 9052 KB 
#include<bits/stdc++.h>

using namespace std;
#define int long long
 
int n, m, ind =0;
vector<pair<pair<int, int>, pair<int ,int>>> edges;
vector<int> parent, spaces, child, order, depth;
vector<vector<int>> adj, dp;
 
void dfs(int u, int pre){
    parent[u] = pre;
    depth[u] = depth[pre]+1;
    for(auto v : adj[u]){
        if(v != pre){
            dfs(v, u);
            spaces[v] = child[u]++;
        }
    }
    order[u] = ind++;
}
 
bool compare(pair<pair<int, int>, pair<int ,int>> a, pair<pair<int, int>, pair<int ,int>> b){
    return order[a.second.second] < order[b.second.second];
}
  
signed main(){
    cin >> n >> m;
    parent.resize(n+5);
    spaces.resize(n+5);
    child.resize(n+5);
    order.resize(n+5);
    depth.resize(n+5);
    adj.resize(n+5);
    dp.resize(n+5, vector<int>(1<<10));
    int sum = 0;
    for(int i = 0; i < m; i++){
        int u, v, c;
        cin >> u >> v >> c;
        if(c == 0){adj[u].push_back(v);adj[v].push_back(u);}
        sum+=c;
        edges.push_back({{u, v}, {c, 0}});
    }
    parent[1] = 1;
    dfs(1, 0);
    for(pair<pair<int, int>, pair<int ,int>>& e : edges){
        int u = e.first.first, v = e.first.second;
        if(depth[u] < depth[v])swap(u, v);
        while(depth[u] > depth[v])u = parent[u];
        while(u != v){u = parent[u]; v = parent[v];}
        e.second.second = u;
    }
    sort(edges.begin(), edges.end(), compare);
    for(pair<pair<int, int>, pair<int ,int>>& e : edges){
        int u = e.first.first, v = e.first.second, lca = e.second.second;
        if(depth[u]%2 != depth[v]%2 && e.second.first != 0)continue;
        int tot = e.second.first;
        int mask1 = 0, mask2 = 0;
        while(u != lca){
            tot+=dp[u][mask1];
            mask1 = 1<<spaces[u];
            u = parent[u];
        }
        while(v != lca){
            tot+=dp[v][mask2];
            mask2 = 1<<spaces[v];
            v = parent[v];
        }
        mask1|=mask2;
        for(int mask = (1<<child[lca])-1; mask >= 0; mask--){
            if((mask & mask1) != 0)continue;
            dp[lca][mask] = max(dp[lca][mask], tot+dp[lca][mask|mask1]);
        }
    }
    int ans = sum-dp[1][0];
    cout << ans << "\n";
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 568 KB Output is correct
2 Correct 0 ms 604 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 0 ms 692 KB Output is correct

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

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

Subtask #9
9.0 / 9.0

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

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 3 ms 4692 KB Output is correct
3 Correct 9 ms 9052 KB Output is correct
4 Correct 4 ms 4700 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9052 KB Output is correct
2 Correct 10 ms 9052 KB Output is correct
3 Correct 7 ms 8920 KB Output is correct
4 Correct 6 ms 9048 KB Output is correct