Submission #1047846

#TimeUsernameProblemLanguageResultExecution timeMemory
1047846ooscodeDesignated Cities (JOI19_designated_cities)C++17
100 / 100
356 ms130896 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define F first #define S second #define pb push_back #define all(x) x.begin() , x.end() const int N = 3e5 + 10; const int INF = 1e18 + 10; const int mod = 1e9 + 7; int n; vector<pair<int , pair<int , int>>> g[N]; int ans[N]; int dp[N]; int dw[N]; int up[N]; vector<int> pre[N]; vector<int> suf[N]; int pos[N]; void efs(int v , int pr) { for(auto [u , w] : g[v]) if(u != pr) { efs(u , v); dp[v] += dp[u] + w.S; } } int root; void rer(int v , int pr) { ans[1] = max(ans[1] , dp[v]); // cout << v << " : " << dp[v] << " " << max(dw[v] , up[v]) << " tet\n"; if(ans[2] < dp[v] + max(dw[v] , up[v])) {ans[2] = dp[v] + max(dw[v] , up[v]) , root = v;} for(auto [u , w] : g[v]) if(u != pr) { dp[v] -= dp[u] + w.S; dp[u] += dp[v] + w.F; rer(u , v); dp[u] -= dp[v] + w.F; dp[v] += dp[u] + w.S; } } void kfs(int v , int pr) { for(auto [u , w] : g[v]) if(u != pr) { kfs(u , v); dw[v] = max(dw[v] , dw[u] + w.F); pos[u] = pre[v].size(); pre[v].pb(dw[v]); } for(int i = g[v].size()-1 ; ~i ; i--) { int u = g[v][i].F; auto w = g[v][i].S; if(u == pr) continue; int x = dw[u] + w.F; if(suf[v].size()) suf[v].pb(max(suf[v].back() , x)); else suf[v].pb(x); } reverse(all(suf[v])); } void lfs(int v , int pr) { for(auto [u , w] : g[v]) if(u != pr) { up[u] = up[v]; int p = pos[u]; if(p != 0) up[u] = max(up[u] , pre[v][p-1]); if(p != suf[v].size() - 1) up[u] = max(up[u] , suf[v][p+1]); up[u] += w.S; lfs(u , v); } } multiset<int> s[N]; void dfs(int v , int pr) { s[v].insert(0); for(auto [u , w] : g[v]) if(u != pr) { dfs(u , v); int x = *(--s[u].end()); s[u].erase(--s[u].end()); s[u].insert(x + w.F); if(s[u].size() > s[v].size()) s[v].swap(s[u]); for(auto p : s[u]) s[v].insert(p); } // cout << v << " :\n"; // for(auto x : s[v]) cout << x << " "; // cout << "\n"; } void solve() { cin >> n; if(n == 2) { int x , y; cin >> x >> y >> x >> y; int q; cin >> q; while(q--) { int z; cin >> z; if(z == 1) cout << min(x , y) << "\n"; else cout << "0\n"; } return; } int f = 0; for(int i = 1 ; i < n ; i++) { int v , u , a , b; cin >> v >> u >> a >> b; f += a + b; g[v].pb({u , {a , b}}); g[u].pb({v , {b , a}}); } // cout << "\n"; kfs(1 , -1); lfs(1 , -1); // for(int i = 1 ; i <= n ; i++) // cout << i << " " << dw[i] << " " << up[i] << "\n"; efs(1 , -1); ans[1] = dp[1]; rer(1 , -1); ans[1] = ans[1]; ans[2] = ans[2]; dfs(root , -1); // cout << root << "\n"; int q; cin >> q; int p = 3; s[root].erase(--s[root].end()); while(s[root].size()) ans[p] = ans[p-1] + *(--s[root].end()) , p++ , s[root].erase(--s[root].end()); while(q--) { int x; cin >> x; cout << f - ans[x] << "\n"; } } /* 4 1 2 1 2 1 3 3 4 1 4 5 6 2 1 2 5 1 2 1 2 2 3 2 3 3 4 3 4 4 5 4 5 5 1 2 3 4 5 */ signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); }

Compilation message (stderr)

designated_cities.cpp: In function 'void lfs(long long int, long long int)':
designated_cities.cpp:74:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         if(p != suf[v].size() - 1) up[u] = max(up[u] , suf[v][p+1]);
      |            ~~^~~~~~~~~~~~~~~~~~~~
#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...