Submission #1202711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202711		SSKMF	Museum (CEOI17_museum)	C++20	100 / 100	219 ms	151668 KiB

museum

#include <bits/stdc++.h>
using namespace std;

vector < pair <int , int> > adiacenta[10001];
vector <int> minim[10001][2];
int dorit;

inline void Parcurgere (const int nod , const int sursa)
{
    minim[nod][0].resize(2);
    minim[nod][1].resize(2);

    for (auto vecin : adiacenta[nod]) {
        if (vecin.first != sursa)
        {
            Parcurgere(vecin.first , nod);

            if ((int)minim[nod][0].size() < dorit)
                { minim[nod][0].resize(min(dorit + 1 , (int)minim[nod][0].size() + (int)minim[vecin.first][0].size() - 1) , 1000000000); }
            if ((int)minim[nod][1].size() < dorit)
                { minim[nod][1].resize(min(dorit + 1 , (int)minim[nod][1].size() + (int)minim[vecin.first][1].size() - 1) , 1000000000); }

            for (int total = (int)minim[nod][0].size() - 1 ; total > 1 ; total--) {
                for (int termen = min(total - 1 , (int)minim[vecin.first][0].size() - 1) ; termen && minim[nod][0][total - termen] != 1000000000 ; termen--) 
                { 
                    minim[nod][1][total] = min({minim[nod][1][total] , minim[nod][1][total - termen] + minim[vecin.first][0][termen] + 2 * vecin.second , minim[nod][0][total - termen] + minim[vecin.first][1][termen] + vecin.second});
                    minim[nod][0][total] = min(minim[nod][0][total] , minim[nod][0][total - termen] + minim[vecin.first][0][termen] + 2 * vecin.second);
                }
            }
        }
    }
}

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int numar_noduri , inceput;
    cin >> numar_noduri >> dorit >> inceput;

    for (int indice = 1 ; indice < numar_noduri ; indice++)
    {
        int nod[2] , cost;
        cin >> nod[0] >> nod[1] >> cost;
        adiacenta[nod[0]].push_back({nod[1] , cost});
        adiacenta[nod[1]].push_back({nod[0] , cost});
    }

    Parcurgere(inceput , 0);
    
    cout << minim[inceput][1][dorit];
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20