Submission #624895

#TimeUsernameProblemLanguageResultExecution timeMemory
624895LoboRoad Closures (APIO21_roads)C++17
24 / 100
26 ms8360 KiB
#include<iostream> #include<vector> #include<cassert> #include<algorithm> #include "roads.h" using namespace std; #define mp make_pair #define fr first #define sc second #define pb push_back #define all(x) x.begin(),x.end() #define sz(x) int32_t(x.size()) #define int long long const int maxn = 2e3+10; const int inf = 1e18+10; const int mnv = -1e15-10; const int mxv = 1e15+10; int n, dp[maxn][2], mark[maxn], atv[maxn]; vector<int> g[maxn], gr[maxn]; vector<pair<int,int>> gesp[maxn]; int cnt[maxn]; vector<int> trq[maxn], trs[maxn], f1[maxn], f2[maxn]; //add/remove pos from id int att(int no, int l, int r, int id, int pos, int val) { // cout << " " << no << " " << l << " " << r << endl; if(l > pos || r < pos) return no; if(no == 0) { no = ++cnt[id]; } //trq[id][trq[id].size()-1] while(no >= sz(f1[id])) { trq[id].pb(0); trs[id].pb(0); f1[id].pb(0); f2[id].pb(0); } if(l == r) { assert(no < sz(trq[id])); trq[id][no]+= val; assert(no < sz(trs[id])); trs[id][no]+= val*pos; return no; } int mid = (l+r)>>1; // cout << no << " -> " << f1[id][no] << endl; // int abc; // f1[id][no] = abc = att(f1[id][no],l,mid,id,pos,val); // assert(no < sz(f1[id])); // f1[id][no] = att(f1[id][no],l,mid,id,pos,val); // int wtf = f1[id][no]; // f1[id][no] = att(wtf,l,mid,id,pos,val); int aux; aux = att(f1[id][no],l,mid,id,pos,val); f1[id][no] = aux; aux = att(f2[id][no],mid+1,r,id,pos,val); f2[id][no] = aux; // f1[id][no] = att(f1[id][no],l,mid,id,pos,val); // f2[id][no] = att(f2[id][no],mid+1,r,id,pos,val); trq[id][no] = trq[id][f1[id][no]]+trq[id][f2[id][no]]; trs[id][no] = trs[id][f1[id][no]]+trs[id][f2[id][no]]; // cout << " " << no << " " << l << " " << r << " " << trq[id][no] << " " << pos << " " << f1[id][no] << " " << f2[id][no] << endl; // cout << aux << endl; // cout << no << " <- " << f1[id][no] << endl; // cout << no << endl; return no; } int find(int no, int l, int r, int id, int val) { // cout << no << " " << l << " " << r << " " << trq[id][no] << " " << trs[id][no] << " " << val << endl; //quero pegar os val menores caras em (l,r) if(no == 0) return 0; if(l == r) { // cout << l << " " << val << endl; return val*r; } int mid = (l+r)>>1; if(trq[id][f1[id][no]] >= val) return find(f1[id][no],l,mid,id,val); else return trs[id][f1[id][no]]+find(f2[id][no],mid+1,r,id,val-trq[id][f1[id][no]]); } void dfs(int u, int qtd, int ant) { mark[u] = 1; int ans = 0; vector<int> use; for(auto V : gesp[u]) if(V.fr != ant) { int v = V.fr; int w = V.sc; dfs(v,qtd,u); ans+= min(dp[v][0],dp[v][1]+w); use.pb(-min(dp[v][0],dp[v][1]+w)+dp[v][1]+w); att(1,mnv,mxv,u,-min(dp[v][0],dp[v][1]+w)+dp[v][1]+w,1); } // sort(all(use)); //se nao tem a aresta com o pai -> sz(g[u])-1-qtd = t dp[u][0] = dp[u][1] = inf; if(sz(g[u])-qtd-1 <= 0) dp[u][1] = ans; else dp[u][1] = ans+find(1,mnv,mxv,u,sz(g[u])-qtd-1); if(sz(g[u])-qtd <= 0) dp[u][0] = ans; else dp[u][0] = ans+find(1,mnv,mxv,u,sz(g[u])-qtd); // cout << " " << u << " " << qtd << " " << sz(g[u]) << " " << ans << " " << find(1,mnv,mxv,u,sz(g[u])-qtd) << endl; for(auto x : use) { att(1,mnv,mxv,u,x,-1); } // for(int i = 1; i <= sz(g[u])-qtd; i++) { // ans+= use[i-1]; // if(i == sz(g[u])-qtd-1) dp[u][1] = ans; // if(i == sz(g[u])-qtd) dp[u][0] = ans; // } } std::vector<int> minimum_closure_costs(int32_t N, std::vector<int32_t> U,std::vector<int32_t> V,std::vector<int32_t> W) { n = N; vector<int> ans; int sumw = 0; for(int i = 0; i < n-1; i++) { int u = U[i]; int v = V[i]; int w = W[i]; sumw+= w; g[u].pb(i); g[v].pb(i); // gesp[u].pb(mp(v,w)); // gesp[v].pb(mp(u,w)); } for(int i = 0; i < n; i++) { cnt[i] = 1; gr[sz(g[i])].pb(i); // trq[i].resize(60*maxn); // trs[i].resize(60*maxn); // f1[i].resize(60*maxn); // f2[i].resize(60*maxn); } vector<int> esp; for(int k = n-1; k >=1; k--) { for(auto i : gr[k]) { atv[i] = 1; // cout << i << endl; esp.pb(i); for(auto id : g[i]) { int v = i^U[id]^V[id]; int w = W[id]; if(atv[v]) { gesp[i].pb(mp(v,w)); gesp[v].pb(mp(i,w)); att(1,mnv,mxv,v,w,-1); } else { // cout << " " << i << " " << v << " " << w << endl; att(1,mnv,mxv,i,w,1); } } } // att(1,mnv,mxv,0,40,1); // cout << " - " << find(1,mnv,mxv,0,1) << endl; int ans1 = 0; for(auto x : esp) { if(!mark[x]) { // cout << x << " " << x << endl; dfs(x,k,-1); ans1+= dp[x][0]; } } // dfs(0,k,-1); ans.pb(ans1); for(auto v : esp) { mark[v] = 0; } } ans.pb(sumw); reverse(all(ans)); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...