oj.uz

Submission #174717

# Submission time Handle Problem Language Result Execution time Memory
174717 2020-01-06T21:30:22 Z stefdasca Museum (CEOI17_museum) C++14
100 / 100
 1333 ms 592768 KB 
#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

// #define fisier

using namespace std;

typedef long long ll;


int add(int a, int b)
{
    ll x = a+b;
    if(x >= mod)
        x -= mod;
    if(x < 0)
        x += mod;
    return x;
}
ll mul(ll a, ll b)
{
    return (a*b) % mod;
}

ll pw(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}
int n, k, x;
int dp[2][10002][10002];
int xtr[10002][10002];

vector<pair<int, int> >v[10002];

vector<int> dp2[2][10002];
vector<int> xtr2[2][10002];
vector<bool> viz2[2][10002];
int sts[10002];
void dfs(int dad, int nod, int cost)
{
    sts[nod] = 1;
    for(int i = 0; i < v[nod].size(); ++i)
    {
        int vecin = v[nod][i].fi;
        if(vecin == dad)
            continue;
        dfs(nod, vecin, v[nod][i].se);
        sts[nod] += sts[vecin];
    }

    dp2[0][nod].resize(sts[nod] + 2, 0);
    dp2[1][nod].resize(sts[nod] + 2, 0);

    xtr2[0][nod].resize(sts[nod] + 2, 0);
    xtr2[1][nod].resize(sts[nod] + 2, 0);

    viz2[0][nod].resize(sts[nod] + 2, 0);
    viz2[1][nod].resize(sts[nod] + 2, 0);


    viz2[0][nod][1] = 1;
    sts[nod] = 1;
    for(int i = 0; i < v[nod].size(); ++i)
    {
        int vecin = v[nod][i].fi;
        if(vecin == dad)
            continue;
        int edcost = v[nod][i].se;
        for(int j = min(k, sts[nod]); j >= 1; --j)
            for(int sz = 1; sz <= min(sts[vecin], k - j); ++sz)
            {
                int trb = 0;
                if(viz2[0][nod][j])
                {
                    if(!viz2[1][nod][j + sz] || dp2[0][nod][j] + dp[1][vecin][sz] + edcost < dp2[1][nod][j + sz])
                    {
                        dp2[1][nod][j + sz] = dp2[0][nod][j] + dp[1][vecin][sz] + edcost;
                        viz2[1][nod][j + sz] = 1;
                        xtr2[1][nod][j + sz] = xtr[vecin][sz];
                    }
                    else
                        if(dp2[0][nod][j] + dp[1][vecin][sz] + edcost == dp2[1][nod][j + sz])
                            xtr2[1][nod][j + sz] = min(xtr2[1][nod][j + sz], xtr[vecin][sz]);
                    if(!viz2[trb][nod][j + sz] || dp2[trb][nod][j] + dp[0][vecin][sz] + 2 * edcost < dp2[trb][nod][j + sz])
                    {
                        dp2[trb][nod][j + sz] = dp2[trb][nod][j] + dp[0][vecin][sz] + 2 * edcost;
                        viz2[trb][nod][j + sz] = 1;
                        xtr2[trb][nod][j + sz] = xtr2[trb][nod][j];
                    }
                    else
                        if(dp2[trb][nod][j] + dp[0][vecin][sz] + 2 * edcost == dp2[trb][nod][j + sz])
                            xtr2[trb][nod][j + sz] = min(xtr2[trb][nod][j + sz], xtr2[trb][nod][j]);
                }
                trb = 1;
                if(viz2[trb][nod][j])
                {
                    if(!viz2[trb][nod][j + sz] || dp2[trb][nod][j] + dp[0][vecin][sz] + 2 * edcost < dp2[trb][nod][j + sz])
                    {
                        dp2[trb][nod][j + sz] = dp2[trb][nod][j] + dp[0][vecin][sz] + 2 * edcost;
                        viz2[trb][nod][j + sz] = 1;
                        xtr2[trb][nod][j + sz] = xtr2[trb][nod][j];
                    }
                    else
                        if(dp2[trb][nod][j] + dp[0][vecin][sz] + 2 * edcost == dp2[trb][nod][j + sz])
                            xtr2[trb][nod][j + sz] = min(xtr2[trb][nod][j + sz], xtr2[trb][nod][j]);
                }
            }
        sts[nod] += sts[vecin];
    }
    for(int i = 2; i <= min(k, sts[nod]); ++i)
    {
        dp[1][nod][i] = dp2[1][nod][i];
        xtr[nod][i] = xtr2[1][nod][i];
        dp[0][nod][i] = dp2[0][nod][i];
    }
    for(int i = 1; i <= min(k, sts[nod]); ++i)
        xtr[nod][i] += cost;
}
int main()
{

    #ifdef fisier
        ifstream f("input.in");
        ofstream g("output.out");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k >> x;
    for(int i = 1; i < n; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].pb({b, c});
        v[b].pb({a, c});
    }
    dfs(0, x, 0);
    cout << dp[1][x][k] << '\n';
    return 0;
}

Compilation message

museum.cpp: In function 'void dfs(int, int, int)':
museum.cpp:58:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); ++i)
                    ~~^~~~~~~~~~~~~~~
museum.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); ++i)
                    ~~^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 4 ms 2424 KB Output is correct
3 Correct 4 ms 2552 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 100272 KB Output is correct
2 Correct 130 ms 100984 KB Output is correct
3 Correct 377 ms 381416 KB Output is correct
4 Correct 211 ms 192376 KB Output is correct
5 Correct 148 ms 124920 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 100272 KB Output is correct
2 Correct 130 ms 100984 KB Output is correct
3 Correct 377 ms 381416 KB Output is correct
4 Correct 211 ms 192376 KB Output is correct
5 Correct 148 ms 124920 KB Output is correct
6 Correct 120 ms 89464 KB Output is correct
7 Correct 288 ms 264312 KB Output is correct
8 Correct 93 ms 47324 KB Output is correct
9 Correct 179 ms 47608 KB Output is correct
10 Correct 100 ms 49656 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 4 ms 2424 KB Output is correct
3 Correct 4 ms 2552 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 127 ms 100272 KB Output is correct
7 Correct 130 ms 100984 KB Output is correct
8 Correct 377 ms 381416 KB Output is correct
9 Correct 211 ms 192376 KB Output is correct
10 Correct 148 ms 124920 KB Output is correct
11 Correct 120 ms 89464 KB Output is correct
12 Correct 288 ms 264312 KB Output is correct
13 Correct 93 ms 47324 KB Output is correct
14 Correct 179 ms 47608 KB Output is correct
15 Correct 100 ms 49656 KB Output is correct
16 Correct 275 ms 102856 KB Output is correct
17 Correct 641 ms 102776 KB Output is correct
18 Correct 367 ms 230484 KB Output is correct
19 Correct 238 ms 47484 KB Output is correct
20 Correct 227 ms 52088 KB Output is correct
21 Correct 1096 ms 368932 KB Output is correct
22 Correct 829 ms 102772 KB Output is correct
23 Correct 929 ms 47864 KB Output is correct
24 Correct 807 ms 52668 KB Output is correct
25 Correct 1333 ms 592768 KB Output is correct