| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1123872 | alir3za_zar3 | Džumbus (COCI19_dzumbus) | C++20 | 0 ms | 0 KiB |
// Alir3za.Zar3 -> Shiraz , Iran #include <bits/stdc++.h> using namespace std; #define int long long #define loop(i , l , r) for (int i=l; i<=r; i+=1) #define arc(i , r , l) for (int i=r; i>=l; i-=1) #define Turbo_In_Out ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define Tc_Management int Tc;cin>>Tc;while(Tc--) const int N = 1e3+10 , Inf = 1e18; int n,m,Dzumbus[N],comp[N]; int dp[N][N],pd[N][N],upd[2][N],sz[N]; vector<int> e[N]; void comp_processor (int v , int par) { comp[v] = par; for (auto to : e[v]) { if (to==par){ continue; } comp_processor(to,v); } } void Combine (int v , int u) { loop(s,0,sz[v]){ loop(z,0,sz[u]){ upd[0][s+z]=upd[1][s+z]=Inf; } } loop(s,0,sz[v]){ loop(z,0,sz[u]){ upd[0][s+z] = min(upd[0][s+z] , dp[v][s]+dp[u][z]); upd[0][s+z] = min(upd[0][s+z] , dp[v][s]+pd[u][z]); upd[0][s+z] = min(upd[0][s+z] , pd[v][s]+dp[u][z]); upd[0][s+z] = min(upd[0][s+z] , pd[v][s]+pd[u][z]); if (s>0) { upd[1][s+z] = min(upd[1][s+z] , pd[v][s]+dp[u][z]); } } } loop(s,0,sz[v]){ loop(z,0,sz[u]){ dp[v][s+z] = min(dp[v][s+z],upd[0][s+z]); pd[v][s+z] = min(pd[v][s+z],upd[1][s+z]); } } sz[v] += sz[u]; } void Combining_DFS (int v , int par) { sz[v]=1; dp[v][0]=0; pd[v][1]=Dzumbus[v]; for (auto to : e[v]) { if (to==par){ continue; } Combining_DFS(to,v); Combine(v,to); } } signed main(){ Turbo_In_Out cin >> n >> m; loop(i,1,n) { cin >> Dzumbus[i]; comp[i]=i; } Dzumbus[0] = Inf; loop(i,0,N-1){ loop(j,0,N-1){ dp[i][j]=pd[i][j]=Inf; } } loop(i,1,m) { int u,v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); } loop(v,1,n) { if (comp[v]==v) { comp_processor(v,0); e[0].push_back(v); } } Combining_DFS(0,0); int q; cin >> q; while (q--) { int S,out; cin >> S; arc(k,n,0) { if (dp[0][k]<=S){ out=k; break; } } cout << out << '\n'; } }