Submission #996872

#	Time	Username	Problem	Language	Result	Execution time	Memory
996872		Ghetto	Training (IOI07_training)	C++17	100 / 100	111 ms	37392 KiB

training

#pragma GCC optimize("O3", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
const short MAX_N = 1e3 + 5, MAX_M = 4e3 + 5;
 
short n, m;
vector<short> adj[MAX_N];
struct Edge {
    short u, v;
    int val;
};
Edge edge[MAX_M];
 
short n_inds, ind[MAX_N], f_ind[MAX_N];
short depth[MAX_N];
short anc[MAX_N][11];
vector<short> children[MAX_N];
short child_ind[MAX_N];
void dfs1(short u = 1, short par = -1) {
    n_inds++, ind[u] = n_inds;
    for (short v : adj[u]) {
        if (v == par) continue;
        anc[v][0] = u, depth[v] = depth[u] + 1;
        children[u].push_back(v), child_ind[v] = children[u].size() - 1;
        dfs1(v, u);
    }
    f_ind[u] = n_inds;
}
void precomp1() {
    dfs1();
    for (short i = 1; i <= 10; i++)
        for (short u = 1; u <= n; u++)
            anc[u][i] = anc[anc[u][i - 1]][i - 1];
}
 
short lca(short u, short v) {
    auto is_anc = [](short u, short v) { return ind[u] <= ind[v] && ind[v] <= f_ind[u]; };
    if (is_anc(u, v)) return u;
    if (is_anc(v, u)) return v;
    
    for (short i = 10; i >= 0; i--) 
        if (anc[u][i] != 0 && !is_anc(anc[u][i], v))
            u = anc[u][i];
    u = anc[u][0];
    return u;
}
int val_sum;
vector<short> paths[MAX_N];
void precomp2() { 
    for (short i = 1; i <= m; i++) {
        val_sum += edge[i].val;
        short w = lca(edge[i].u, edge[i].v);
        short len = depth[edge[i].u] + depth[edge[i].v] - 2 * depth[w] + 1;
        if (len % 2 == 0) continue;
        paths[w].push_back(i);        
    }
}
 
vector<int> dp[MAX_N];
int trans[MAX_M];
void dfs2(short u = 1) {
    dp[u].resize(1 << children[u].size());
    for (short v : children[u]) dfs2(v);
 
    vector<vector<short>> path_children(paths[u].size());
    vector<unordered_map<short, short>> path_child(paths[u].size());
    vector<vector<short>> path(paths[u].size()); // These will use the path's index in u
    for (short j = 0; j < paths[u].size(); j++) {
        short i = paths[u][j];
        short w = lca(edge[i].u, edge[i].v);
        path[j].push_back(w);
        short x = edge[i].u;
        while (true) {
            if (x == w) break;
            path[j].push_back(x);
            if (anc[x][0] == w) path_children[j].push_back(x);
            else path_child[j][anc[x][0]] = x;
            x = anc[x][0];
        }
        x = edge[i].v;
        while (true) {
            if (x == w) break;
            path[j].push_back(x);
            if (anc[x][0] == w) path_children[j].push_back(x);
            else path_child[j][anc[x][0]] = x;
            x = anc[x][0];
        }
        trans[i] = edge[i].val;
        for (short v : path[j]) {
            if (v == u) continue;
            int mask = (1 << children[v].size()) - 1;
            if (path_child[j][v]) mask ^= (1 << child_ind[path_child[j][v]]);
            trans[i] += dp[v][mask];
        }
    }
 
    for (int mask = 0; mask <= (1 << children[u].size()) - 1; mask++) {
        for (short i = 0; i <= (short) children[u].size() - 1; i++) {
            if (!(mask & (1 << i))) continue;
            short v = children[u][i];
            dp[u][mask] += dp[v][(1 << children[v].size()) - 1];
        }

        for (short j = 0; j < paths[u].size(); j++) {
            short i = paths[u][j];
            bool halt = false;
            for (short v : path_children[j])
                if (!(mask & (1 << child_ind[v]))) halt = true;
            if (halt) continue;
            int new_mask = mask;
            for (short v : path_children[j]) new_mask ^= (1 << child_ind[v]);
            dp[u][mask] = max(dp[u][mask], dp[u][new_mask] + trans[i]);
        }
        // cout << u << " " << mask << ": " << dp[u][mask] << endl;
    }
}
 
int main() {
    // freopen("train.in", "r", stdin);
    cin >> n >> m;
    short new_m = 0;
    for (short i = 1; i <= m; i++) {
        short u, v; int val; cin >> u >> v >> val;
        if (val == 0) adj[u].push_back(v), adj[v].push_back(u);
        else new_m++, edge[new_m] = {u, v, val}; 
    }
    m = new_m;
    
    precomp1();
    precomp2();
    dfs2();
 
    int ans = val_sum - dp[1][(1 << children[1].size()) - 1];
    cout << ans << '\n';
}

Compilation message (stderr)

training.cpp: In function 'void dfs2(short int)':
training.cpp:68:25: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (short j = 0; j < paths[u].size(); j++) {
      |                       ~~^~~~~~~~~~~~~~~~~
training.cpp:104:29: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for (short j = 0; j < paths[u].size(); j++) {
      |                           ~~^~~~~~~~~~~~~~~~~

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