Submission #167077

#TimeUsernameProblemLanguageResultExecution timeMemory
167077hentai_loverHard route (IZhO17_road)C++14
19 / 100
2059 ms123524 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #pragma GCC optimize("-O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #define pb push_back #define fr(i, l, r) for(ll i = l; i <= r; ++ i) #define rf(i, l, r) for(ll i = l; i >= r; -- i) using namespace std; using namespace __gnu_pbds; template <typename T> using _set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef int ll; typedef pair<ll, ll> pll; const ll oo = ll(1e9) + 10; const ll N = 5010; ll f[N][N]; ll n, x, y, now; vector <ll> g[N]; unordered_map <ll, ll> mp; void dfs(ll x, ll s = 0, ll p = -1){ f[now][x] = s; for(auto i : g[x]) if(i != p){ dfs(i, s + 1, x); f[now][x] = max(f[now][x], f[now][i]); } } void dfs2(ll x, ll s = 0, ll pp = -1, ll nw = 0){ ll m1 = nw, m2 = nw; for(auto i : g[x]) if(i != pp){ if(m1 <= f[x][i])m2 = m1, m1 = f[x][i]; else if(m2 <= f[x][i])m2 = f[x][i]; } for(auto i : g[x]){ if(i != pp){ if(f[x][i] != m1){ dfs2(i, s + 1, x, m1); } else{ dfs2(i, s + 1, x, m2); } } } //cout << "x = " << x << " nw = " << nw << " s = " << s << " now = " << now << endl; if(g[x].size() == 1 && s != 0){ //cout << "true" << endl; mp[nw * s] ++; } } int main() { //ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n; fr(i, 2, n){ cin >> x >> y; g[x].pb(y); g[y].pb(x); } fr(i, 1, n){ now = i; dfs(i); } fr(i, 1, n){ if(g[i].size() == 1){ now = i; dfs2(i); } } pll ans; for(auto i : mp){ pll z = i; ans = max(ans, z); } cout << ans.first << ' ' << ans.second / 2 << endl; } /* 3 3 1 5 1 2 3 1 3 5 2 3 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...