oj.uz

Submission #119538

# Submission time Handle Problem Language Result Execution time Memory
119538 2019-06-21T11:13:45 Z win11905 Training (IOI07_training) C++11
100 / 100
 16 ms 4608 KB 
#include <bits/stdc++.h>
#define iii tuple<int, int, int>
using namespace std;

const int N = 1e3+5;

int n, m, ans;
vector<int> g[N];
vector<iii> vec, pre[N];
int dep[N], par[N][10];

void init_lca(int u, int p) {
    dep[u] = dep[p] + 1, par[u][0] = p;
    for(int i = 1; i < 10; ++i) par[u][i] = par[par[u][i-1]][i-1];
    if(p) g[u].erase(find(g[u].begin(), g[u].end(), p));
    for(int v : g[u]) init_lca(v, u);
}

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

int dp[N][1<<10];
int pos[N];
int ss[N];

void solve(int u) {
    int sz = g[u].size();
    int sbit = 1 << sz;
    ss[u] = sbit-1;
    for(int i = 0; i < sz; ++i) pos[g[u][i]] = i;
    for(int v : g[u]) {
        solve(v);
        for(int i = 0; i < sbit; ++i) if(i >> pos[v] & 1) dp[u][i] = max(dp[u][i], dp[u][i ^ (1 << pos[v])] + dp[v][ss[v]]);
    }
    for(auto x : pre[u]) {
        int a, b, w; tie(a, b, w) = x;
        int prea = -1, preb = -1;
        int suma = 0, sumb = 0;
        while(a != u) {
            if(prea != -1) suma += dp[a][ss[a] ^ (1 << pos[prea])];
            else suma += dp[a][ss[a]];
            prea = a;
            a = par[a][0];
        }
        while(b != u) {
            if(preb != -1) sumb += dp[b][ss[b] ^ (1 << pos[preb])];
            else sumb += dp[b][ss[b]];
            preb = b;
            b = par[b][0];
        }
        int bt = 0;
        if(prea != -1) bt |= (1 << pos[prea]);
        if(preb != -1) bt |= (1 << pos[preb]);
        for(int i = 0; i < sbit; ++i) if((i & bt) == bt) {
            dp[u][i] = max(dp[u][i], dp[u][i ^ bt] + suma + sumb + w);
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 0, u, v, w; i < m; ++i) {
        scanf("%d %d %d", &u, &v, &w);
        if(!w) g[u].emplace_back(v), g[v].emplace_back(u);
        else vec.emplace_back(u, v, w);
    }
    init_lca(1, 0);
    int sum = 0;
    for(auto x : vec) {
        int u, v, w; tie(u, v, w) = x;
        int dist = dep[u] + dep[v] - 2 * dep[lca(u, v)];
        if(dist & 1) ans += w;
        else {
            pre[lca(u, v)].emplace_back(x);
            sum += w;
        }
    }
    solve(1);
    printf("%d\n", ans + (sum - dp[1][ss[1]]));
}

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", &u, &v, &w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 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 9 ms 4608 KB Output is correct
2 Correct 9 ms 4608 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 512 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 1024 KB Output is correct
2 Correct 4 ms 896 KB Output is correct
3 Correct 6 ms 1664 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2176 KB Output is correct
2 Correct 9 ms 1408 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 4 ms 896 KB Output is correct
2 Correct 4 ms 1664 KB Output is correct
3 Correct 15 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 8 ms 2176 KB Output is correct
2 Correct 16 ms 4504 KB Output is correct
3 Correct 8 ms 1792 KB Output is correct
4 Correct 8 ms 1536 KB Output is correct