oj.uz

Submission #784276

# Submission time Handle Problem Language Result Execution time Memory
784276 2023-07-16T00:09:58 Z phoebe Training (IOI07_training) C++17
0 / 100
 55 ms 83368 KB 
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define PB push_back
#define ALL(x) x.begin(), x.end()
#define FOR(i, n) for (int i = 0; i < n; i++)
#define NYOOM ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
const int INF = 1e9 + 7;
const ll LLINF = 1ll<<60;

const int maxn = 1e3 + 10;
int n, m, h[maxn], jump[maxn][11], get_idx[maxn], dp[10][1<<10][maxn];
map<pii, int> path;
vector<int> adj[maxn], x[maxn];
vector<pair<pii, int>> edge;
vector<pair<pii, pii>> connections[maxn]; // {{cost, child}, {node, node_child}}

void dfs(int v, int p, int height){
    jump[v][0] = p; h[v] = height;
    int idx = 0;
    for (auto u : adj[v]){
        if (u == p) continue;
        get_idx[u] = idx++; x[v].PB(u);
        dfs(u, v, height + 1);
    }
}

void lca_add(int a, int b, int c){
    // h[a] >= h[b]
    int start_a = a, start_b = b;
    for (int p = 10; p >= 0; p--){
        if (h[jump[a][p]] > h[b]) a = jump[a][p];
    }
    if (jump[a][0] == b){
        connections[a].PB({{c, a}, {b, start_a}});
        return;
    }
    if (h[jump[a][0]] == h[b]) a = jump[a][0];
    for (int p = 10; p >= 0; p--){
        if (jump[a][p] != jump[b][p]) a = jump[a][p], b = jump[b][p];
    }
    connections[a].PB({{c, start_a}, {b, start_b}});
    connections[b].PB({{c, start_b}, {a, start_a}});
}

int solve(int idx, int mask, int p);

int path_cost(int p, int v){
    if (path.count({p, v})) return path[{p, v}];
    int re = 0, last = -1;
    while (v != p){
        int mask = 0; 
        if (last != -1) mask |= (1<<get_idx[last]);
        re += solve(0, mask, v);
        // cout << "a " << solve(0, mask, v) << endl;
        last = v;
        v = jump[v][0];
    }
    // cout << v << ' ' << re << endl;
    path[{p, v}] = re;
    return re;
}

int solve(int idx, int mask, int p){
    if (idx >= x[p].size()) return 0;
    if (dp[idx][mask][p] != -1) return dp[idx][mask][p];
    int v = x[p][idx];
    int re = solve(idx + 1, mask, p); // takent
    if (mask&(1<<idx)) return re;
    re += solve(0, 0, v);
    int take_mask = mask|(1<<idx);
    for (auto c : connections[v]){
        int cost = c.F.F, child = c.F.S, u = c.S.F, u_child = c.S.S;
        if (get_idx[u] < idx) continue;
        int take = 0;
        if (u == p){ // connects to parent
            // cout << v << ' ' << u << endl;
            take = solve(idx + 1, take_mask, p) + cost;
            take += path_cost(p, u_child);
        }
        else{
            assert(false);
            take = solve(idx + 1, take_mask|(1<<get_idx[u]), p) + cost;
            take += path_cost(p, child);
            take += path_cost(p, u_child);
        }
        re = max(re, take);
    }
    dp[idx][mask][p] = re;
    return dp[idx][mask][p];
}

signed main(){
    NYOOM;
    fill(&dp[0][0][0], &dp[0][0][0] + 10 * (1<<10) * maxn, -1);
    cin >> n >> m;
    int sum = 0;
    FOR(i, m){
        int a, b, c; cin >> a >> b >> c;
        sum += c;
        if (c == 0){
            adj[a].PB(b); adj[b].PB(a);
        }
        else{
            edge.PB({{a, b}, c});
        }
    }
    dfs(1, 1, 0);
    for (int p = 1; p <= 10; p++){
        for (int i = 1; i <= n; i++){
            jump[i][p] = jump[jump[i][p - 1]][p - 1];
        }
    }
    for (auto x : edge){
        int a = x.F.F, b = x.F.S, c = x.S;
        if (abs(h[a] - h[b]) % 2){ 
            // if connects two nodes odd dist apart = can't include
            continue;
        }
        if (h[a] < h[b]) swap(a, b);
        lca_add(a, b, c);
    }
    cout << sum - solve(0, 0, 1);
}

Compilation message

training.cpp: In function 'int solve(int, int, int)':
training.cpp:71:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     if (idx >= x[p].size()) return 0;
      |         ~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 82676 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 82724 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 55 ms 83260 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 82728 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 82716 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 82724 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 82780 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 82988 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 83320 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 83060 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 51 ms 83368 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -