oj.uz

Submission #120106

# Submission time Handle Problem Language Result Execution time Memory
120106 2019-06-23T11:13:39 Z PeppaPig Training (IOI07_training) C++14
100 / 100
 17 ms 4724 KB 
#include <bits/stdc++.h>

#define iii tuple<int, int, int>
#define long long long

using namespace std;

const int N = 1e3+5;

int n, m;
vector<int> g[N];
vector<iii> E, res[N];

int par[N][12], dep[N];

void pre_process(int u, int p) {
    dep[u] = dep[p] + 1, par[u][0] = p;
    for(int i = 1; i < 12; i++) par[u][i] = par[par[u][i-1]][i-1];
    for(int v : g[u]) if(v != p) pre_process(v, u); 
}

int lca(int a, int b) {
    if(dep[a] < dep[b]) swap(a, b);
    for(int i = 11; ~i; i--) if(dep[par[a][i]] >= dep[b]) a = par[a][i];
    if(a == b) return a;
    for(int i = 11; ~i; i--) if(par[a][i] != par[b][i]) a = par[a][i], b = par[b][i];
    return par[a][0];
}

long ans, sum, dp[N][1 << 10];
int bit[N], pos[N];

void dfs(int u, int p) {
    int sz = g[u].size();
    bit[u] = (1 << sz) - 1;
    for(int i = 0; i < sz; i++) if(g[u][i] != p) pos[g[u][i]] = i;
    for(int v : g[u]) if(v != p) {
        dfs(v, u);
        for(int i = 0; i <= bit[u]; i++) if(i >> pos[v] & 1)
            dp[u][i] = max(dp[u][i], dp[u][i ^ (1 << pos[v])] + dp[v][bit[v]]);
    }
    for(iii e : res[u]) {
        int a, b, c; tie(a, b, c) = e;
        long sum_a = 0, sum_b = 0;
        int pv_a = -1, pv_b = -1;

        while(a != u) {
            if(pv_a != -1) sum_a += dp[a][bit[a] ^ (1 << pos[pv_a])];
            else sum_a += dp[a][bit[a]];
            pv_a = a, a = par[a][0];
        }
        while(b != u) {
            if(pv_b != -1) sum_b += dp[b][bit[b] ^ (1 << pos[pv_b])];
            else sum_b += dp[b][bit[b]];
            pv_b = b, b = par[b][0];
        }
        int x = 0;
        if(pv_a != -1) x ^= 1 << pos[pv_a];
        if(pv_b != -1) x ^= 1 << pos[pv_b];
        for(int i = 0; i <= bit[u]; i++) if((x & i) == x)
            dp[u][i] = max(dp[u][i], dp[u][i ^ x] + sum_a + sum_b + c);
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1, a, b, c; i <= m; i++) {
        scanf("%d %d %d", &a, &b, &c);
        if(!c) g[a].emplace_back(b), g[b].emplace_back(a);
        else E.emplace_back(a, b, c); 
    }
    pre_process(1, 0);
    for(iii e : E) {
        int a, b, c; tie(a, b, c) = e;
        int l = lca(a, b), d = dep[a] + dep[b] - 2 * dep[l];
        if(d & 1) ans += c;
        else {
            res[l].emplace_back(a, b, c);
            sum += c;
        }
    }
    dfs(1, 0);
    printf("%lld\n", ans + sum - dp[1][bit[1]]);

    return 0;
}

Compilation message

training.cpp: In function 'int main()':
training.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
training.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4608 KB Output is correct
2 Correct 10 ms 4724 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1152 KB Output is correct
2 Correct 4 ms 896 KB Output is correct
3 Correct 7 ms 1792 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2176 KB Output is correct
2 Correct 9 ms 1792 KB Output is correct
3 Correct 6 ms 1536 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1192 KB Output is correct
2 Correct 5 ms 1664 KB Output is correct
3 Correct 17 ms 4608 KB Output is correct
4 Correct 5 ms 1792 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2304 KB Output is correct
2 Correct 17 ms 4608 KB Output is correct
3 Correct 10 ms 2048 KB Output is correct
4 Correct 9 ms 1920 KB Output is correct