oj.uz

답안 #1090334

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1090334 2024-09-18T08:59:36 Z _callmelucian Training (IOI07_training) C++14
100 / 100
 58 ms 4700 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 4700 KB Output is correct
2 Correct 10 ms 4700 KB Output is correct

Subtask #4
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 600 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1116 KB Output is correct
2 Correct 3 ms 860 KB Output is correct
3 Correct 35 ms 1628 KB Output is correct

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2140 KB Output is correct
2 Correct 45 ms 1364 KB Output is correct
3 Correct 5 ms 1628 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 856 KB Output is correct
2 Correct 2 ms 1628 KB Output is correct
3 Correct 58 ms 4680 KB Output is correct
4 Correct 3 ms 1884 KB Output is correct

Subtask #11
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 2316 KB Output is correct
2 Correct 39 ms 4692 KB Output is correct
3 Correct 21 ms 1760 KB Output is correct
4 Correct 47 ms 1616 KB Output is correct