Submission #451816

#	Time	Username	Problem	Language	Result	Execution time	Memory
451816		prvocislo	Training (IOI07_training)	C++17	100 / 100	30 ms	8248 KiB

training

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
typedef long long ll;
using namespace std;

const int maxn = 1005, maxm = 5005, deg = 10;
void upd(int& a, const int& b) { a = max(a, b); }
struct edge { int u, v, cost, lca; };
vector<edge> e;
int dp[maxn][1 << deg], depth[maxn], p[maxn], pos[maxn][maxn], n, m;
vector<int> g[maxn];
vector<int> ord;
void dfs(int u)
{
    if (u) g[u].erase(find(g[u].begin(), g[u].end(), p[u]));
    for (int i = 0; i < g[u].size(); i++)
    {
        depth[g[u][i]] = depth[u] + 1, p[g[u][i]] = u, pos[u][g[u][i]] = (1 << i);
        dfs(g[u][i]);
    }
    ord.push_back(u);
}
int lca(int u, int v)
{
    if (depth[u] < depth[v]) swap(u, v);
    while (depth[u] > depth[v]) u = p[u];
    while (u != v) u = p[u], v = p[v];
    return u;
}
int all(int x) { return (1 << g[x].size()) - 1; }
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    int sum = 0;
    for (int i = 0, a, b, c; i < m; i++)
    {
        cin >> a >> b >> c; a--, b--;
        sum += c;
        if (!c) g[a].push_back(b), g[b].push_back(a);
        else e.push_back({ a, b, c, -1 });
    }
    dfs(0);
    for (int i = 0; i < e.size(); i++)
    {
        if ((depth[e[i].u] & 1) == (depth[e[i].v] & 1)) e[i].lca = lca(e[i].u, e[i].v);
        else e[i].lca = -1;
    }
    for (int u : ord)
    {
        for (const edge& i : e) if (i.lca == u)
        {
            int e1 = 0, e2 = 0, ans = i.cost;
            for (int v1 = i.u; v1 != u; e1 = pos[p[v1]][v1], v1 = p[v1]) ans += dp[v1][all(v1) ^ e1];
            for (int v2 = i.v; v2 != u; e2 = pos[p[v2]][v2], v2 = p[v2]) ans += dp[v2][all(v2) ^ e2];
            int take = e1 | e2;
            for (int mask = 0; mask < (1 << g[u].size()); mask++) if ((mask & take) == 0)
            {
                upd(dp[u][mask | take], dp[u][mask] + ans);
            }
        }
        for (int mask = 0; mask < (1 << g[u].size()); mask++)
        {
            for (int i = 0; i < g[u].size(); i++) if (!(mask & (1 << i)))
                upd(dp[u][mask | (1 << i)], dp[u][mask] + dp[g[u][i]][all(g[u][i])]);
        }
    }
    cout << sum - dp[0][all(0)] << "\n";
    return 0;
}

Compilation message (stderr)

training.cpp: In function 'void dfs(int)':
training.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i = 0; i < g[u].size(); i++)
      |                     ~~^~~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 0; i < e.size(); i++)
      |                     ~~^~~~~~~~~~
training.cpp:67:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             for (int i = 0; i < g[u].size(); i++) if (!(mask & (1 << i)))
      |                             ~~^~~~~~~~~~~~~

• 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