Submission #1090334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090334		_callmelucian	Training (IOI07_training)	C++14	100 / 100	58 ms	4700 KiB

training

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

int up[1010][11], depth[1010], num[1010], sz[1010], timeDfs;
int dp[1010][1 << 10], dpFull[1010], calc[1010];

vector<int> adj[1010];
vector<tt> paths[1010];

int preDfs (int u, int p, int d) {
    up[u][0] = p, depth[u] = d, num[u] = ++timeDfs, sz[u] = 1;
    for (int i = 1; i < 11; i++)
        up[u][i] = up[up[u][i - 1]][i - 1];
    for (int v : adj[u])
        if (v != p) sz[u] += preDfs(v, u, d + 1);
    return sz[u];
}

int goUp (int a, int k) {
    for (int i = 0; i < 11; i++)
        if (k & (1 << i)) a = up[a][i];
    return a;
}

int lca (int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    a = goUp(a, depth[a] - depth[b]);
    if (a == b) return a;
    for (int i = 10; i >= 0; i--)
        if (up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];
    return up[a][0];
}

bool getCur (int mask, int pos) {
    return mask & (1 << pos);
}

int cur;

void dfs (int u, int p) {
    calc[u] = cur + dpFull[u];
    int fullMask = (1 << adj[u].size()) - 1;
    for (int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i]; if (v == p) continue;
        cur += dp[u][fullMask ^ (1 << i)];
        dfs(v, u);
        cur -= dp[u][fullMask ^ (1 << i)];
    }
}

bool inTree (int root, int u) {
    return num[root] <= num[u] && num[u] < num[root] + sz[root];
}

void solve (int u, int p) {
    for (int v : adj[u]) {
        if (v == p) continue;
        solve(v, u), dfs(v, u);
    }

    for (int allow = 0; allow < (1 << adj[u].size()); allow++) {
        for (int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i];
            if (!getCur(allow, i) || v == p) continue;
            dp[u][allow] += dpFull[v];
        }

        for (tt path : paths[u]) {
            int a, b, cost, mask = 0; tie(a, b, cost) = path;
            for (int i = 0; i < adj[u].size(); i++) {
                int v = adj[u][i]; if (v == p) continue;
                if (inTree(v, a)) mask |= (1 << i);
                if (inTree(v, b)) mask |= (1 << i);
            }

            if ((allow & mask) == mask)
                dp[u][allow] = max(dp[u][allow], dp[u][allow ^ mask] + calc[a] + calc[b] + cost);
        }
    }
    dpFull[u] = dp[u][(1 << adj[u].size()) - 1];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m, sum = 0; cin >> n >> m;
    vector<tt> unpaved;

    for (int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        if (c) {
            unpaved.emplace_back(a, b, c);
            sum += c;
        }
        else {
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
    }
    preDfs(1, 1, 1);

    for (tt it : unpaved) {
        int a, b, c; tie(a, b, c) = it;
        if (depth[a] % 2 == depth[b] % 2)
            paths[lca(a, b)].push_back(it);
    }
    solve(1, 1);

    cout << sum - dpFull[1];

    return 0;
}

Compilation message (stderr)

training.cpp: In function 'void dfs(int, int)':
training.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i = 0; i < adj[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
training.cpp: In function 'void solve(int, int)':
training.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int i = 0; i < adj[u].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~
training.cpp:79:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             for (int i = 0; i < adj[u].size(); 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