Submission #1041228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041228		ThommyDB	Training (IOI07_training)	C++17	100 / 100	10 ms	9052 KiB

training

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 7 / 7
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9