제출 #1209020

#제출 시각아이디문제언어결과실행 시간메모리
1209020HanksburgerDesignated Cities (JOI19_designated_cities)C++20
7 / 100
1303 ms63352 KiB
#include <bits/stdc++.h> #define int long long using namespace std; vector<pair<int, pair<int, int> > > adj[200005]; int ans[200005], sumsum, cnt; void dfs1(unordered_map<int, int> &mp, vector<int> &sz, int u, int p) { for (int i=0; i<adj[u].size(); i++) { int v=adj[u][i].first; if (v==p || !mp[v]) continue; dfs1(mp, sz, v, u); sz[mp[u]]+=sz[mp[v]]; } } int dfs2(unordered_map<int, int> &mp, vector<int> &sz, int u, int p, int n) { for (int i=0; i<adj[u].size(); i++) { int v=adj[u][i].first; if (v==p || !mp[v]) continue; if (sz[mp[v]]*2>n) return dfs2(mp, sz, v, u, n); } return u; } vector<int> *dfs3(unordered_map<int, int> &mp, int u, int p) { vector<int> *ans=new vector<int>; for (int i=0; i<adj[u].size(); i++) { int v=adj[u][i].first, w=adj[u][i].second.first; if (v==p || !mp[v]) continue; vector<int> *res=dfs3(mp, v, u); (*res)[0]+=w; if (ans->size()<res->size()) swap(ans, res); if (res->empty()) { delete res; continue; } if ((*ans)[0]<(*res)[0]) swap((*ans)[0], (*res)[0]); for (int x:*res) ans->push_back(x); delete res; } if (ans->empty()) ans->push_back(0); //cout << u << ": "; //for (int x:*ans) // cout << x << ' '; //cout << '\n'; return ans; } void dfs4(unordered_map<int, int> &mp, vector<int> &sum, int u, int p) { for (int i=0; i<adj[u].size(); i++) { int v=adj[u][i].first, w=adj[u][i].second.first; if (v==p || !mp[v]) continue; dfs4(mp, sum, v, u); sum[mp[u]]+=sum[mp[v]]+w; } } void dfs5(unordered_map<int, int> &mp, vector<int> &tmp, int u, int p) { //cout << "dfs5 " << u << '\n'; tmp.push_back(u); for (int i=0; i<adj[u].size(); i++) { int v=adj[u][i].first; if (v==p || !mp[v]) continue; dfs5(mp, tmp, v, u); } } void recur(vector<int> &vec, int offset) { int n=vec.size(); if (n<=2) return; //cout << "recur "; //for (int x:vec) // cout << x << ' '; //cout << '\n'; unordered_map<int, int> mp; vector<pair<int, int> > dp; vector<int> sum(n+1, 0), sz(n+1, 1); for (int i=0; i<n; i++) mp[vec[i]]=i+1; dfs1(mp, sz, vec[0], 0); int centroid=dfs2(mp, sz, vec[0], 0, n); //cout << "centroid = " << centroid << '\n'; for (int i=0; i<adj[centroid].size(); i++) { int v=adj[centroid][i].first, w=adj[centroid][i].second.first; if (!mp[v]) continue; vector<int> *res=dfs3(mp, v, centroid); (*res)[0]+=w; for (int x:*res) dp.push_back({x, i}); delete res; } //cout << "here\n"; sort(dp.begin(), dp.end(), greater<pair<int, int> >()); dfs4(mp, sum, centroid, 0); int cur=0, ind=0; //cout << "dp: "; //for (int i=0; i<dp.size(); i++) //{ // cout << dp[i].first << ' ' << dp[i].second << '\n'; //} for (int i=1; i<dp.size(); i++) { if (dp[i-1].second!=dp[i].second) { ind=i; break; } } //cout << "sum = " << sum[mp[centroid]] << '\n'; for (int i=2; i<=dp.size(); i++) { cur+=dp[i-2].first; ans[i]=min(ans[i], sum[mp[centroid]]-cur-dp[max(ind, i-1)].first+offset); } //cout << "here\n"; for (int i=0; i<adj[centroid].size(); i++) { //cout << "i=" << i << '\n'; int v=adj[centroid][i].first, w1=adj[centroid][i].second.first, w2=adj[centroid][i].second.second; if (!mp[v]) continue; vector<int> tmp; dfs5(mp, tmp, v, centroid); recur(tmp, offset+sum[mp[centroid]]-sum[mp[v]]-w1+w2); } } void calc1(int u, int p) { int leaf=1; for (int i=0; i<adj[u].size(); i++) { int v=adj[u][i].first, w=adj[u][i].second.first; if (v==p) continue; calc1(v, u); sumsum+=w; leaf=0; } if (leaf) cnt++; } void calc2(int u, int p, int offset) { ans[1]=min(ans[1], offset); for (int i=0; i<adj[u].size(); i++) { int v=adj[u][i].first, w1=adj[u][i].second.first, w2=adj[u][i].second.second; if (v==p) continue; calc2(v, u, offset-w1+w2); } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, q; cin >> n; for (int i=1; i<n; i++) { int u, v, w1, w2; cin >> u >> v >> w1 >> w2; adj[u].push_back({v, {w1, w2}}); adj[v].push_back({u, {w2, w1}}); } vector<int> tmp(n); for (int i=1; i<=n; i++) tmp[i-1]=i, ans[i]=1e18; recur(tmp, 0); calc1(1, 0); calc2(1, 0, sumsum); for (int i=cnt+1; i<=n; i++) ans[i]=ans[cnt]; cin >> q; for (int i=1; i<=q; i++) { int x; cin >> x; cout << ans[x] << '\n'; } }
#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...