oj.uz

Submission #794129

# Submission time Handle Problem Language Result Execution time Memory
794129 2023-07-26T09:39:32 Z boyliguanhan Training (IOI07_training) C++17
30 / 100
 11 ms 8348 KB 
#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++;
    int temp[1024]{};
    for(int mask = 0; mask < 1<<cnt; mask++)
        for(int i = 0; i < cnt; i++)
            if(!(mask&1<<i))
                temp[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])))
                temp[mask] = max(temp[mask],dp[n][mask|bit[x.a]|bit[x.b]]+res);
    }
    swap(dp[n], temp);
}
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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7124 KB Output is correct
2 Correct 11 ms 8348 KB Output is correct

Subtask #4
0 / 7.0

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

Subtask #5
0 / 9.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 9.0

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