oj.uz

Submission #451816

# Submission time Handle Problem Language Result Execution time Memory
451816 2021-08-03T12:12:44 Z prvocislo Training (IOI07_training) C++17
100 / 100
 30 ms 8248 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7756 KB Output is correct
2 Correct 14 ms 7836 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 716 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1228 KB Output is correct
2 Correct 2 ms 972 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1484 KB Output is correct
2 Correct 3 ms 1356 KB Output is correct
3 Correct 5 ms 2508 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3940 KB Output is correct
2 Correct 10 ms 1928 KB Output is correct
3 Correct 12 ms 2732 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1100 KB Output is correct
2 Correct 5 ms 2764 KB Output is correct
3 Correct 28 ms 8248 KB Output is correct
4 Correct 7 ms 2892 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3788 KB Output is correct
2 Correct 30 ms 7628 KB Output is correct
3 Correct 13 ms 2892 KB Output is correct
4 Correct 11 ms 2536 KB Output is correct