Submission #1210410

#TimeUsernameProblemLanguageResultExecution timeMemory
1210410ammahmed004Museum (CEOI17_museum)C++20
0 / 100
502 ms1114112 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define FAST ios::sync_with_stdio(0), cin.tie(0),cout.tie(0) #define ll long long #define ld long double #define int long long #define endl "\n" #define yes cout<<"YES"<<endl; #define no cout<<"NO"<<endl; #define pb push_back //#pragma GCC optimize("O3,unroll-loops") //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") using namespace std; const int MOD = 1e9+7 ; //const int MOD = 998244353 ; const int N = 1e5+5 ; const ll INF = 1e18 ; const ll MIN = -1e18 ; typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> indexed_set; void solve() { ll n,k,x;cin>>n>>k>>x; vector<pair<ll,ll>> g[n+1]; for(int i=1;i<n;i++){ ll u,v,c;cin>>u>>v>>c; g[u].pb({v,c}); g[v].pb({u,c}); } vector<vector<ll>> dp(n+1,vector<ll>(k+1,INF)); vector<ll> childs(n+1,1); ll ans=INF; function<void(int,int)> dfs=[&](int v,int p){ dp[v][1]=dp[v][0]=0; for(auto [child,cost] : g[v]){ if(child == p)continue; vector<ll> temp(k+1,INF); for(int i=0;i<=min(k,childs[v]);i++){ temp[i]=dp[v][i]; } for(int i=0;i<=min(k-1,childs[child]);i++){ temp[i+1]=min(temp[i+1],dp[child][i]+cost); } for(int i=1;i<=min(k,childs[v]);i++){ for(int j=0;j<=min(k,childs[child]) && j+i<=k;j++){ ll sum=i+j; ll c=min(dp[v][i]*2+dp[child][j]+cost,(dp[child][j]+cost)*2+dp[v][i]); temp[sum]=min(temp[sum],cost); } } childs[v]+=childs[child]; for(int i=2;i<=min(k,childs[v]);i++){ dp[v][i]=min(dp[v][i],temp[i]); } } }; dfs(x,0); cout<<dp[x][k]<<endl; } signed main() { FAST; auto begin = std::chrono::high_resolution_clock::now(); #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif ll t=1; cin>>t; while(t--) solve(); #ifndef ONLINE_JUDGE auto end = std::chrono::high_resolution_clock::now(); cout << setprecision(4) << fixed; cout << "Execution time: " << std::chrono::duration_cast<std::chrono::duration<double>>(end - begin).count() << " seconds" << endl; #endif }

Compilation message (stderr)

museum.cpp: In function 'int main()':
museum.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         freopen("input.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen("output.txt","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...