제출 #1198173

#제출 시각아이디문제언어결과실행 시간메모리
1198173walizamaneeMuseum (CEOI17_museum)C++20
0 / 100
41 ms52292 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; /*using namespace __gnu_pbds; template <typename T> using indexed_set = tree< T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update >; // indexed_set<int> s; // and use s.insert(x), s.erase(x), // *s.find_by_order(k), s.order_of_key(x), etc. using ll = long long; */ vector<pair<int ,unsigned int>> adj[10001]; int n , k , x , ek , dui , siz[10001]; unsigned int one[10001][10001] , two[10001][10001] , c , uno , dos; void getans( int me , int par ) { siz[me] = 1; for( int z = 0; z < (int)adj[me].size(); z++ ) { if( adj[me][z].first != par ) { getans( adj[me][z].first , me ); dui = siz[me]; siz[me] += siz[adj[me][z].first]; for( int zz = min( k , siz[me]); zz > 1; zz-- ) { for( int y = min( zz - 1 , siz[adj[me][z].first]) ; (y > 0 && zz - y <= dui); y-- ) { c = one[me][zz - y] + one[adj[me][z].first][y] + (2 * adj[me][z].second); one[me][zz] = min( one[me][zz] , c ); c = min( two[me][zz - y] + one[adj[me][z].first][y] + (2 * adj[me][z].second) , one[me][zz - y] + two[adj[me][z].first][y] + adj[me][z].second ); two[me][zz] = min( two[me][zz] , c ); } } } } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> k >> x; for( int z = 1; z < n; z++ ) { cin >> ek >> dui >> c; adj[ek].push_back({dui , c}); adj[dui].push_back({ek , c}); } getans( x , 0 ); cout << min( one[x][k] , two[x][k] ) << "\n"; 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...