Submission #1202709

#TimeUsernameProblemLanguageResultExecution timeMemory
1202709SSKMFMuseum (CEOI17_museum)C++20
80 / 100
3095 ms18092 KiB
#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 adancime , 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 , adancime + 1 , nod); if ((int)minim[nod][0].size() < dorit - adancime + 1) { minim[nod][0].resize(min(dorit - adancime + 1 , (int)minim[nod][0].size() + (int)minim[vecin.first][0].size() - 1) , 1000000000); } if ((int)minim[nod][1].size() < dorit - adancime + 1) { minim[nod][1].resize(min(dorit - adancime + 1 , (int)minim[nod][1].size() + (int)minim[vecin.first][1].size() - 1) , 1000000000); } for (int total = (int)minim[nod][1].size() - 1 ; total > 1 ; total--) { for (int termen = min(total - 1 , (int)minim[vecin.first][1].size() - 1) ; termen ; 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}); } } 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 ; termen--) { 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 , 0); cout << minim[inceput][1][dorit]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...