oj.uz

Submission #174715

# Submission time Handle Problem Language Result Execution time Memory
174715 2020-01-06T21:25:16 Z stefdasca Museum (CEOI17_museum) C++14
100 / 100
 2780 ms 592896 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 dp2[2][10002][10002];
int xtr2[2][10002][10002];
bool viz2[2][10002][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 trb = 0; trb <= 1; ++trb)
                for(int sz = 1; sz <= min(sts[vecin], k - j); ++sz)
                {
                    if(!viz2[trb][nod][j])
                        continue;
                    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]);
                    if(trb == 0)
                    {
                        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]);
                    }
                }
        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;
    /*
    cout << nod << '\n';
    for(int i = 1; i <= sts[nod]; ++i)
        cout << dp[0][nod][i] << " ";
    cout << '\n';
    for(int i = 1; i <= sts[nod]; ++i)
        cout << dp[1][nod][i] << " ";
    cout << '\n';
    for(int i = 1; i <= sts[nod]; ++i)
        cout << xtr[nod][i] << " ";
    cout << '\n';
    */
}
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:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); ++i)
                    ~~^~~~~~~~~~~~~~~
museum.cpp:83: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 2552 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 130 ms 100424 KB Output is correct
2 Correct 130 ms 100984 KB Output is correct
3 Correct 378 ms 381432 KB Output is correct
4 Correct 213 ms 192376 KB Output is correct
5 Correct 150 ms 124836 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 100424 KB Output is correct
2 Correct 130 ms 100984 KB Output is correct
3 Correct 378 ms 381432 KB Output is correct
4 Correct 213 ms 192376 KB Output is correct
5 Correct 150 ms 124836 KB Output is correct
6 Correct 121 ms 89464 KB Output is correct
7 Correct 286 ms 264168 KB Output is correct
8 Correct 99 ms 47480 KB Output is correct
9 Correct 101 ms 47736 KB Output is correct
10 Correct 104 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 2552 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 130 ms 100424 KB Output is correct
7 Correct 130 ms 100984 KB Output is correct
8 Correct 378 ms 381432 KB Output is correct
9 Correct 213 ms 192376 KB Output is correct
10 Correct 150 ms 124836 KB Output is correct
11 Correct 121 ms 89464 KB Output is correct
12 Correct 286 ms 264168 KB Output is correct
13 Correct 99 ms 47480 KB Output is correct
14 Correct 101 ms 47736 KB Output is correct
15 Correct 104 ms 49656 KB Output is correct
16 Correct 256 ms 102624 KB Output is correct
17 Correct 644 ms 102660 KB Output is correct
18 Correct 379 ms 230440 KB Output is correct
19 Correct 290 ms 47608 KB Output is correct
20 Correct 230 ms 52088 KB Output is correct
21 Correct 1125 ms 368876 KB Output is correct
22 Correct 815 ms 102932 KB Output is correct
23 Correct 1147 ms 47948 KB Output is correct
24 Correct 813 ms 52600 KB Output is correct
25 Correct 2780 ms 592896 KB Output is correct