Submission #589808

#TimeUsernameProblemLanguageResultExecution timeMemory
589808HuyDžumbus (COCI19_dzumbus)C++17
110 / 110
45 ms11252 KiB
/// no sound please #include<bits/stdc++.h> #define int long long #define pii pair<int,int> #define pic pair<int,char> #define fi first #define se second /*#pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma")*/ using namespace std; using ll = long long; using ull = unsigned long long; using ldb = long double; const ll N = (int)1e9 + 1; const int maxN = (int)2e5 + 2; const int mod = 1e9 + 7; //const int mod = 998244353; const ll infty = 1e18 + 7; const int base = (int)4e5; void InputFile() { //freopen("IELTS.inp","r",stdin); //freopen("IELTS.out","w",stdout); //freopen("test.out","r",stdin); } void FastInput() { ios_base::sync_with_stdio(false); cin.tie(nullptr); } int n,m; int d[2000]; vector<int> adj[2000]; vector<ll> dp[2000][3]; /// 0 : ko chon i /// 1 : chon i va i ke dinh khac /// 2 : chon i nhung i dell ke dinh khac int grp = 0; int subsz[2000]; vector<ll> f; void Read() { cin >> n >> m; for(int i = 1; i <= n; i++) { cin >> d[i]; } for(int i = 1; i <= m; i++) { int x,y; cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); } } void PreDFS(int u,int p) { subsz[u] = 1; for(int v : adj[u]) { if(v == p) continue; PreDFS(v,u); subsz[u] += subsz[v]; } } void DFS(int u,int p) { dp[u][0] = {0,infty}; dp[u][1] = {infty,infty}; dp[u][2] = {infty,d[u]}; int ss = 1; for(int v : adj[u]) { if(v == p) continue; DFS(v,u); vector<ll> vc[3]; vc[0].resize(ss + subsz[v] + 1,infty); vc[1].resize(ss + subsz[v] + 1,infty); vc[2].resize(ss + subsz[v] + 1,infty); for(int i = 0;i <= ss;i++) { for(int j = 0;j <= subsz[v];j++) { vc[0][i+j] = min(vc[0][i+j],dp[u][0][i] + dp[v][0][j]); vc[0][i+j] = min(vc[0][i+j],dp[u][0][i] + dp[v][1][j]); vc[1][i+j] = min(vc[1][i+j],dp[u][1][i] + dp[v][0][j]); vc[1][i+j] = min(vc[1][i+j],dp[u][1][i] + dp[v][1][j]); vc[1][i+j] = min(vc[1][i+j],dp[u][1][i] + dp[v][2][j]); vc[1][i+j] = min(vc[1][i+j],dp[u][2][i] + dp[v][2][j]); vc[1][i+j] = min(vc[1][i+j],dp[u][2][i] + dp[v][1][j]); vc[2][i+j] = min(vc[2][i+j],dp[u][2][i] + dp[v][0][j]); } } swap(vc[0],dp[u][0]); swap(vc[1],dp[u][1]); swap(vc[2],dp[u][2]); ss += subsz[v]; } } void Solve() { for(int i = 1;i <= n;i++) { if(subsz[i] == 0) PreDFS(i,i); } int su = 0; f = {0}; vector<ll> sf; for(int u = 1;u <= n;u++) { if(dp[u][0].empty()) { DFS(u,u); sf.resize(su + subsz[u] + 1,infty); for(int i = 0;i <= su;i++) { for(int j = 0;j <= subsz[u];j++) { sf[i+j] = min(sf[i+j],f[i] + dp[u][0][j]); sf[i+j] = min(sf[i+j],f[i] + dp[u][1][j]); } } swap(sf,f); sf.clear(); su += subsz[u]; } } for(int i = f.size() - 2;i >= 0;i--) { f[i] = min(f[i],f[i+1]); } int q; cin >> q; while(q--) { int val; cin >> val; cout << upper_bound(f.begin(),f.end(),val) - f.begin() - 1 <<'\n'; } } void Debug() { } int32_t main() { FastInput(); //InputFile(); //int sub_type; //cin >> sub_type; //Sieve(); //Prepare(); int test; //cin >> test; test = 1; while(test--) //for(int prc = 1; prc <= test; prc++) { Read(); Solve(); //Debug(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...