Submission #984993

#TimeUsernameProblemLanguageResultExecution timeMemory
984993a_l_i_r_e_z_aHard route (IZhO17_road)C++17
100 / 100
725 ms114232 KiB
// In the name of God // Hope is last to die #include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") // #pragma GCC optimize("avx2") typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define pb push_back // #define int long long #define S second #define F first #define mp make_pair #define smax(xyxy, yxy) (xyxy) = max((xyxy), (yxy)) #define smin(xyxy, yxy) (xyxy) = min((xyxy), (yxy)) #define all(xyxy) (xyxy).begin(), (xyxy).end() #define len(xyxy) ((int)(xyxy).size()) const int maxn = 5e5 + 5; const int inf = 1e9 + 7; ll n, cnt[maxn]; pll dpu[maxn], dpd[maxn]; pll ans = mp(0, 1); vector<int> adj[maxn]; void smaxp(pll &x, pll y, int v){ if(y.F + v > x.F) x = mp(y.F + v, y.S); else if(y.F + v == x.F) x.S += y.S; } void dfsd(int v = 1, int p = 0){ dpd[v] = mp(0, 1); for(auto u: adj[v]) if(u != p){ dfsd(u, v); smaxp(dpd[v], dpd[u], 1); } } void dfsu(int v = 1, int p = 0){ int mx1 = -1, mx2 = -1; for(auto u: adj[v]) if(u != p){ if(mx1 == -1 || dpd[u].F >= dpd[mx1].F){ mx2 = mx1; mx1 = u; } else if(mx2 == -1 || dpd[u].F > dpd[mx2].F) mx2 = u; smaxp(dpu[u], dpu[v], 1); } for(auto u: adj[v]) if(u != p){ if(u == mx1){ if(mx2 != -1){ smaxp(dpu[u], dpd[mx2], 2); } } else smaxp(dpu[u], dpd[mx1], 2); dfsu(u, v); } } void dfs(int v = 1, int p = 0){ vector<pll> vec; for(auto u: adj[v]) if(u != p){ dfs(u, v); vec.pb(mp(dpd[u].F + 1, dpd[u].S)); } if(v > 1) vec.pb(dpu[v]); if(vec.size() < 3) return; sort(all(vec), greater<>()); ll val = vec[1].F + vec[2].F; ll res = 0; for(int i = 1; i < vec.size(); i++){ res += vec[i].S * cnt[val - vec[i].F]; cnt[vec[i].F] += vec[i].S; } if(vec[2].F == vec[0].F){ for(int i = 1; i < vec.size() && vec[i].F == vec[0].F; i++){ res += vec[i].S * vec[0].S; } } else if(vec[1].F == vec[0].F){ res += (res / vec[1].S) * vec[0].S; } smaxp(ans, mp(vec[0].F * val, res), 0); for(auto u: vec) cnt[u.F] = 0; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for(int i = 0; i < n - 1; i++){ int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } dfsd(); for(int i = 1; i <= n; i++) dpu[i] = mp(0, 1); dfsu(); // for(int i = 1; i <= n; i++){ // cout << i << ' ' << dpd[i].F << ' ' << dpd[i].S << ' ' << dpu[i].F << ' ' << dpu[i].S << '\n'; // } dfs(); cout << ans.F << ' ' << ans.S << '\n'; return 0; }

Compilation message (stderr)

road.cpp: In function 'void dfs(int, int)':
road.cpp:77:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i = 1; i < vec.size(); i++){
      |                    ~~^~~~~~~~~~~~
road.cpp:82:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for(int i = 1; i < vec.size() && vec[i].F == vec[0].F; i++){
      |                        ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...