oj.uz

Submission #174714

# Submission time Handle Problem Language Result Execution time Memory
174714 2020-01-06T21:11:01 Z stefdasca Museum (CEOI17_museum) C++14
80 / 100
 3000 ms 381196 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;
        sts[nod] += sts[vecin];
        int edcost = v[nod][i].se;
        for(int j = min(k, sts[nod]); j >= 0; --j)
            for(int trb = 0; trb <= 1; ++trb)
                for(int sz = 1; sz <= min(j, sts[vecin]); ++sz)
                {
                    if(!viz2[trb][nod][j - sz])
                        continue;
                    if(!viz2[trb][nod][j] || dp2[trb][nod][j - sz] + dp[0][vecin][sz] + 2 * edcost < dp2[trb][nod][j])
                    {
                        dp2[trb][nod][j] = dp2[trb][nod][j - sz] + dp[0][vecin][sz] + 2 * edcost;
                        viz2[trb][nod][j] = 1;
                        xtr2[trb][nod][j] = xtr2[trb][nod][j - sz];
                    }
                    else
                        if(dp2[trb][nod][j - sz] + dp[0][vecin][sz] + 2 * edcost == dp2[trb][nod][j])
                            xtr2[trb][nod][j] = min(xtr2[trb][nod][j], xtr2[trb][nod][j - sz]);
                    if(trb == 0)
                    {
                        if(!viz2[1][nod][j] || dp2[0][nod][j - sz] + dp[1][vecin][sz] + edcost < dp2[1][nod][j])
                        {
                            dp2[1][nod][j] = dp2[0][nod][j - sz] + dp[1][vecin][sz] + edcost;
                            viz2[1][nod][j] = 1;
                            xtr2[1][nod][j] = xtr[vecin][sz];
                        }
                        else
                            if(dp2[0][nod][j - sz] + dp[1][vecin][sz] + edcost == dp2[1][nod][j])
                                xtr2[1][nod][j] = min(xtr2[1][nod][j], xtr[vecin][sz]);
                    }
                }
    }
    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 135 ms 100060 KB Output is correct
2 Correct 137 ms 100856 KB Output is correct
3 Correct 570 ms 381196 KB Output is correct
4 Correct 252 ms 192376 KB Output is correct
5 Correct 179 ms 124920 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 100060 KB Output is correct
2 Correct 137 ms 100856 KB Output is correct
3 Correct 570 ms 381196 KB Output is correct
4 Correct 252 ms 192376 KB Output is correct
5 Correct 179 ms 124920 KB Output is correct
6 Correct 126 ms 89468 KB Output is correct
7 Correct 347 ms 264252 KB Output is correct
8 Correct 97 ms 47352 KB Output is correct
9 Correct 99 ms 47736 KB Output is correct
10 Correct 106 ms 49828 KB Output is correct

Subtask #4
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 135 ms 100060 KB Output is correct
7 Correct 137 ms 100856 KB Output is correct
8 Correct 570 ms 381196 KB Output is correct
9 Correct 252 ms 192376 KB Output is correct
10 Correct 179 ms 124920 KB Output is correct
11 Correct 126 ms 89468 KB Output is correct
12 Correct 347 ms 264252 KB Output is correct
13 Correct 97 ms 47352 KB Output is correct
14 Correct 99 ms 47736 KB Output is correct
15 Correct 106 ms 49828 KB Output is correct
16 Correct 359 ms 102688 KB Output is correct
17 Correct 1526 ms 102776 KB Output is correct
18 Execution timed out 3057 ms 216328 KB Time limit exceeded
19 Halted 0 ms 0 KB -