Submission #915641

#	Time	Username	Problem	Language	Result	Execution time	Memory
915641		Trisanu_Das	Training (IOI07_training)	C++17	Compilation error	0 ms	0 KiB

training

#include <bits/stdc++.h>
 
using namespace std;
 
struct edge {
    int a, b, c, lca;
};
 
vector<edge> edges, fe;
int total = 0;
vector<int> adj[1005];
 
int tin[1005], timer = 1;
int jmp[1005][12], depth[1005];
int col[1005];
pair<int, int> par[1005];
int deg[1005];
int dp[1005][1 << 11];
 
void dfs(int node) {
    tin[node] = timer++;
    for (int i = 1; i < 12; i++) jmp[node][i] = jmp[jmp[node][i-1]][i-i];
    for (auto nxt : adj[node]) {
        if (tin[nxt]) continue;
        if (col[node] == 1) col[nxt] = 2;
        else col[nxt] = 1;
        par[nxt] = {node, (1 << deg[node]++)};
        depth[nxt] = depth[node] + 1;
        jmp[nxt][0] = node;
        dfs(nxt);
    }
}
 
int lca(int a, int b) {
    if (depth[a] > depth[b]) swap(a, b);
    for (int i = 11; i >= 0; i--) if (depth[jmp[b][i]] >= depth[a]) b = jmp[b][i];
    if (a == b) return a;
    for (int i = 11; i >= 0; i--) if (jmp[a][i] != jmp[b][i]) a = jmp[a][i]; b = jmp[b][i];
    return jmp[a][0];
}
 
int main() {
    int n, m; cin >> n >> m;
 
    for (int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        total += c;
        if (c == 0) adj[a].push_back(b); adj[b].push_back(a);
        edges.push_back({a, b, c});
    }
    col[1] = 1;
    jmp[1][0] = 1;
    depth[1] = 1;
    dfs(1);
    for (auto e: edges) {
        if (col[e.a] == col[e.b]) fe.push_back({e.a, e.b, e.c, lca(e.a, e.b)});
        else if (e.c == 0) fe.push_back({e.a, e.b, e.c, lca(e.a, e.b)});
    }
    sort(fe.begin(), fe.end(), [&](edge a, edge b) {
        return tin[a.lca] > tin[b.lca];
    });
    for (auto e : fe) {
        int tot = e.c;
        int finalmask = 0;
        int mask = 0;
        for (int i = e.a; i != e.lca; mask = par[i].second, i = par[i].first) tot += dp[i][mask];
        finalmask |= mask;
        mask = 0;
        for (int i = e.b; i != e.lca;mask = par[i].second, i = par[i].first) tot += dp[i][mask];
        finalmask |= mask;
        for (int mk = (1 << deg[e.lca]) - 1; mk >= 0 ; mk--) {
            if (mk & finalmask) continue;
            dp[e.lca][mk] = max(dp[e.lca][mk], dp[e.lca][mk | finalmask] + tot);
        }
    }
    cout << total - dp[1][0];
}

Compilation message (stderr)

training.cpp: In function 'int lca(int, int)':
training.cpp:38:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   38 |     for (int i = 11; i >= 0; i--) if (jmp[a][i] != jmp[b][i]) a = jmp[a][i]; b = jmp[b][i];
      |     ^~~
training.cpp:38:78: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   38 |     for (int i = 11; i >= 0; i--) if (jmp[a][i] != jmp[b][i]) a = jmp[a][i]; b = jmp[b][i];
      |                                                                              ^
training.cpp:38:89: error: 'i' was not declared in this scope
   38 |     for (int i = 11; i >= 0; i--) if (jmp[a][i] != jmp[b][i]) a = jmp[a][i]; b = jmp[b][i];
      |                                                                                         ^
training.cpp: In function 'int main()':
training.cpp:48:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   48 |         if (c == 0) adj[a].push_back(b); adj[b].push_back(a);
      |         ^~
training.cpp:48:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   48 |         if (c == 0) adj[a].push_back(b); adj[b].push_back(a);
      |                                          ^~~