Submission #784276

#	Time	Username	Problem	Language	Result	Execution time	Memory
784276		phoebe	Training (IOI07_training)	C++17	0 / 100	55 ms	83368 KiB

training

#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 (stderr)

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
• 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