Submission #119535

# Submission time Handle Problem Language Result Execution time Memory
119535 2019-06-21T11:05:20 Z win11905 Training (IOI07_training) C++11
0 / 100
14 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 < g[u].size(); ++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) {
            suma += dp[a][ss[a] ^ (1 << (prea == -1 ? 0 : pos[prea]))];
            prea = a;
            a = par[a][0];
        }
        while(b != u) {
            sumb += dp[b][ss[b] ^ (1 << (preb == -1 ? 0 : pos[preb]))];
            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 'void solve(int)':
training.cpp:35:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < g[u].size(); ++i) pos[g[u][i]] = i;
                    ~~^~~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:64: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:66: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);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 4608 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 612 KB Output is correct
2 Incorrect 3 ms 640 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 768 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1024 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2176 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 9 ms 2176 KB Output is correct
2 Incorrect 14 ms 4608 KB Output isn't correct
3 Halted 0 ms 0 KB -