oj.uz

Submission #174718

# Submission time Handle Problem Language Result Execution time Memory
174718 2020-01-06T21:32:11 Z stefdasca Museum (CEOI17_museum) C++14
100 / 100
 1049 ms 592648 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)
            {
                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]);
                for(int trb = 0; trb <= 1; ++trb)
                {
                    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:78: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 2552 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 121 ms 100088 KB Output is correct
2 Correct 137 ms 100896 KB Output is correct
3 Correct 387 ms 381328 KB Output is correct
4 Correct 206 ms 192120 KB Output is correct
5 Correct 164 ms 124788 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 100088 KB Output is correct
2 Correct 137 ms 100896 KB Output is correct
3 Correct 387 ms 381328 KB Output is correct
4 Correct 206 ms 192120 KB Output is correct
5 Correct 164 ms 124788 KB Output is correct
6 Correct 124 ms 89336 KB Output is correct
7 Correct 272 ms 264128 KB Output is correct
8 Correct 89 ms 47224 KB Output is correct
9 Correct 91 ms 47480 KB Output is correct
10 Correct 97 ms 49632 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2552 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 121 ms 100088 KB Output is correct
7 Correct 137 ms 100896 KB Output is correct
8 Correct 387 ms 381328 KB Output is correct
9 Correct 206 ms 192120 KB Output is correct
10 Correct 164 ms 124788 KB Output is correct
11 Correct 124 ms 89336 KB Output is correct
12 Correct 272 ms 264128 KB Output is correct
13 Correct 89 ms 47224 KB Output is correct
14 Correct 91 ms 47480 KB Output is correct
15 Correct 97 ms 49632 KB Output is correct
16 Correct 205 ms 102508 KB Output is correct
17 Correct 446 ms 102672 KB Output is correct
18 Correct 317 ms 230392 KB Output is correct
19 Correct 193 ms 47452 KB Output is correct
20 Correct 174 ms 51960 KB Output is correct
21 Correct 816 ms 368632 KB Output is correct
22 Correct 556 ms 102776 KB Output is correct
23 Correct 739 ms 47608 KB Output is correct
24 Correct 540 ms 52544 KB Output is correct
25 Correct 1049 ms 592648 KB Output is correct