oj.uz

Submission #54029

# Submission time Handle Problem Language Result Execution time Memory
54029 2018-07-02T08:36:57 Z Costin Andrei Oncescu(#1302) Training (IOI07_training) C++11
100 / 100
 13 ms 1808 KB 
#include<bits/stdc++.h>

using namespace std;

int currSz, N, M, t[5009], niv[5009], x[5009], y[5009], z[5009], msk[5009], code[1009], realId[1009];
long long dp[1009], oth[1009], sumAll[1009], extra[5009], bitDp[1 << 11];
vector < int > v[1009], h[1009];

void dfs (int nod)
{
    for (auto it : v[nod])
        if (it != t[nod])
            niv[it] = niv[nod] + 1, t[it] = nod, dfs (it);
}

int lca (int x, int y)
{
    while (x != y)
    {
        if (niv[x] > niv[y]) x = t[x];
        else y = t[y];
    }
    return x;
}

void solve (int nod)
{
    for (auto it : v[nod])
        if (it != t[nod])
            solve (it);
    currSz = 0;
    for (auto it : v[nod])
        if (it != t[nod])
            code[it] = currSz ++,
            realId[currSz - 1] = it;
    for (auto i : h[nod])
    {
        int a = x[i], b = y[i];
        extra[i] = z[i];
        while (a != nod && t[a] != nod)
            extra[i] += oth[a], a = t[a];
        while (b != nod && t[b] != nod)
            extra[i] += oth[b], b = t[b];
        if (x[i] != nod)
            extra[i] += dp[x[i]];
        if (y[i] != nod)
            extra[i] += dp[y[i]];
        msk[i] = 0;
        if (a != nod)
            msk[i] |= 1 << code[a];
        if (b != nod)
            msk[i] |= 1 << code[b];
    }
    for (int i=0; i<1 << currSz; i++)
        bitDp[i] = 0;
    for (int i=0; i<1 << currSz; i++)
    {
        for (auto j : h[nod])
            if ((msk[j] & i) == 0 && bitDp[i | msk[j]] < bitDp[i] + extra[j])
                bitDp[i | msk[j]] = bitDp[i] + extra[j];
        for (int j=0; j<currSz; j++)
            if ((i & (1 << j)) == 0 && bitDp[i | (1 << j)] < bitDp[i] + dp[realId[j]])
                bitDp[i | (1 << j)] = bitDp[i] + dp[realId[j]];
    }
    dp[nod] = bitDp[(1 << currSz) - 1];
    for (int i=0; i<currSz; i++)
        oth[realId[i]] = bitDp[((1 << currSz) - 1) ^ (1 << i)];
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d", &N, &M);
for (int i=1; i<=M; i++)
{
    scanf ("%d %d %d", &x[i], &y[i], &z[i]);
    if (z[i] == 0)
        v[x[i]].push_back (y[i]),
        v[y[i]].push_back (x[i]);
}
dfs (1);
long long ans = 0, all = 0;
for (int i=1; i<=M; i++)
{
    if (niv[x[i]] % 2 != niv[y[i]] % 2)
        ans += z[i], z[i] = 0;
    if (z[i] != 0)
        h[lca (x[i], y[i])].push_back (i), all += z[i];
}
solve (1);
printf ("%lld\n", ans + all - dp[1]);
return 0;
}

Compilation message

training.cpp: In function 'int main()':
training.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d %d", &N, &M);
 ~~~~~~^~~~~~~~~~~~~~~~~
training.cpp:78:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d %d", &x[i], &y[i], &z[i]);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 748 KB Output is correct
2 Correct 6 ms 1000 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1040 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct
3 Correct 6 ms 1152 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1252 KB Output is correct
2 Correct 10 ms 1252 KB Output is correct
3 Correct 5 ms 1372 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1372 KB Output is correct
2 Correct 4 ms 1372 KB Output is correct
3 Correct 13 ms 1452 KB Output is correct
4 Correct 4 ms 1452 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1568 KB Output is correct
2 Correct 12 ms 1752 KB Output is correct
3 Correct 10 ms 1752 KB Output is correct
4 Correct 10 ms 1808 KB Output is correct