oj.uz

Submission #447141

# Submission time Handle Problem Language Result Execution time Memory
447141 2021-07-24T17:44:20 Z SirCovidThe19th Training (IOI07_training) C++14
100 / 100
 19 ms 4588 KB 
#include <bits/stdc++.h>
using namespace std; 

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

const int mx = 1005;

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

void dfs(int i){ 
    for (int x : adj[i]) 
        if (x != par[i]) 
            dep[x] = dep[i]+1, par[x] = i, pos[x] = (1<<deg[i]++), dfs(x); 
}int LCA(int a, int b){
    while (dep[a] > dep[b]) a = par[a]; 
    while (dep[b] > dep[a]) b = par[b]; 
    while (a != b) a = par[a], b = par[b];
    return a;
}void solve(int i){
    for (int x : adj[i]) 
        if (x != par[i]) 
            solve(x);
    for (int msk = 0; msk < (1<<deg[i]); msk++)
        for (int x : adj[i]) 
            if (x != par[x] and !(msk&pos[x])) 
                dp[i][msk] += dp[x][0];
    for (auto r : evenPth[i]){
        int sum = r.w, p1 = 0, p2 = 0;
        for (int x = r.a; x != i; p1 = pos[x], x = par[x]) sum += dp[x][p1];
        for (int x = r.b; x != i; p2 = pos[x], x = par[x]) sum += dp[x][p2];
        for (int msk = 0; msk < (1<<deg[i]); msk++)
            if (!(msk&p1) and !(msk&p2))
                dp[i][msk] = max(dp[i][msk], dp[i][(msk|p1|p2)]+sum);
    }
}

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);
        else noPave.push_back({a, b, w});
    }dfs(1); 
    for (auto r : noPave) 
        if ((dep[r.a]+dep[r.b])%2 == 0)
            evenPth[LCA(r.a, r.b)].push_back(r);
    solve(1); cout<<ans-dp[1][0]<<endl;    
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4428 KB Output is correct
2 Correct 16 ms 4556 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1484 KB Output is correct
2 Correct 2 ms 1612 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2380 KB Output is correct
2 Correct 4 ms 2380 KB Output is correct
3 Correct 5 ms 2380 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4492 KB Output is correct
2 Correct 10 ms 4556 KB Output is correct
3 Correct 7 ms 4556 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2380 KB Output is correct
2 Correct 4 ms 2412 KB Output is correct
3 Correct 18 ms 4532 KB Output is correct
4 Correct 5 ms 2484 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4556 KB Output is correct
2 Correct 19 ms 4588 KB Output is correct
3 Correct 11 ms 4576 KB Output is correct
4 Correct 9 ms 4556 KB Output is correct