Submission #794119

#	Time	Username	Problem	Language	Result	Execution time	Memory
794119		boyliguanhan	Training (IOI07_training)	C++17	10 / 100	7 ms	4436 KiB

training

#include<bits/stdc++.h>
using namespace std;
vector<int> adj[1024];
struct npe {
    int a, b, c;
};
vector<npe>b[1024],edge;
int dep[1024], p[1024];
void dfs(int n) {
    for(auto i: adj[n])
        if(i!=p[n])
            p[i] = n, dep[i] = dep[n]+1, dfs(i);
}
int lca(int a, int b){
    while(dep[a]>dep[b]) a = p[a];
    while(dep[b]>dep[a]) b = p[b];
    while(a-b) a = p[a], b = p[b];
    return a;
}
int dp[1024][1024], bit[1024], ith[10];
void solve(int n) {
    int cnt = 0;
    for(auto i: adj[n])
        if(i!=p[n])
            solve(i);
    for(auto i: adj[n])
        if(i!=p[n])
            ith[cnt] = i, bit[i] = 1<<cnt++;
    for(int mask = 0; mask < 1<<cnt; mask++)
        for(int i = 0; i < cnt; i++)
            if(!(mask&1<<i))
                dp[n][mask]+=dp[ith[i]][0];
    for(auto x: b[n]) {
        int res = x.c, a = x.a, b = x.b;
        if(a!=n){
            res+=dp[a][0];
            for(;p[a]!=n;a=p[a])
                res+=dp[p[a]][bit[a]];
        }
        if(b!=n){
            res+=dp[b][0];
            for(;p[b]!=n;b=p[b])
                res+=dp[p[b]][bit[b]];
        }
        for(int mask = 0; mask < 1<<cnt; mask++)
            if(!(mask&(bit[x.a]|bit[x.b])))
                dp[n][mask] = max(dp[n][mask],dp[n][mask|bit[x.a]|bit[x.b]]+res);
    }
}
int main() {
    int n, m,sum=0;
    cin >> n >> m;
    while(m--) {
        int a, b, c;
        cin >> a >> b >> c;
        if(c)
            edge.push_back({a,b,c}), sum+=c;
        else
            adj[a].push_back(b),adj[b].push_back(a);
    }
    dfs(1);
    for(npe i: edge)
        if(1^(dep[i.a]+dep[i.b])%2)
        b[lca(i.a,i.b)].push_back(i);
    solve(1);
    cout << sum - dp[1][0] << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 7
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9