Submission #1216028

#TimeUsernameProblemLanguageResultExecution timeMemory
1216028M_SH_OHard route (IZhO17_road)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h> //#include "grader.h" /*#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp>*/ #define ll long long #define ll1 long long #define ull unsigned long long #define dou long double #define str string #define vll vector<ll> #define vi vector<int> #define pll pair<ll, ll> #define vpll vector<pll> #define vbool vector<bool> #define vstr vector<str> #define vvll vector<vll> #define pb push_back #define pf push_front #define endl "\n" #define fr first #define se second // #define sortcmp(a) sort(a.begin(), a.end(), cmp) #define sort(a) sort(a.begin(), a.end()) #define all(a) a.begin(), a.end() #define reverse(a) reverse(a.begin(), a.end()) #define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define INF 1000000000000000000 #define ordered_set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update> using namespace std; //using namespace __gnu_pbds; mt19937 rng(1488); ll randll(ll l, ll r){ return uniform_int_distribution<ll>(l, r)(rng); } /*vector<map<ll, vll>> s; vll p; ll find(ll v) { if (p[v] == v) return v; return p[v] = find(p[v]); } void unite(ll a, ll b) { a = find(a); b = find(b); if (a == b) return; if (s[a].size() < s[b].size()) { p[a] = b; for (auto i : s[a]) { for (int j : i.se) { s[b][i.fr].pb(j); } } s[a].clear(); } else { p[b] = a; for (auto i : s[b]) { for (int j : i.se) { s[a][i.fr].pb(j); } } s[b].clear(); } } vll tree1, d; void push(ll v, ll tl, ll tr) { if (tl == tr) return; tree1[v*2] += d[v]; tree1[v*2+1] += d[v]; d[v*2] += d[v]; d[v*2+1] += d[v]; d[v] = 0; tree1[v] = tree1[v*2]+tree1[v*2+1]; } void bt(ll v, ll tl, ll tr, vll& a) { if (tl == tr) { tree1[v] = a[tl]; return; } ll tm = (tl+tr)/2; bt(v*2, tl, tm, a); bt(v*2, tm+1, tr, a); tree1[v] = tree1[v*2]+tree1[v*2+1]; } ll get(ll l, ll r, ll v, ll tl, ll tr) { if (l <= tl && tr <= r) return tree1[v]; if (tl > r || tr < l) return 0; ll tm = (tl+tr)/2; push(v, tl, tr); return get(l, r, v*2, tl, tm)+get(l, r, v*2+1, tm+1, tr); } void update(ll l, ll r, ll val, ll v, ll tl, ll tr) { if (l <= tl && tr <= r) { tree1[v] += val; d[v] += val; push(v, tl, tr); return; } if (tl > r || tr < l) return; ll tm = (tl+tr)/2; push(v, tl, tr); update(l, r, val, v*2, tl, tm); update(l, r, val, v*2+1, tm+1, tr); tree1[v] = tree1[v*2]+tree1[v*2+1]; }*/ vvll g; vpll dp; void dfs(ll v, ll p = -1) { if (g[v].size() == 1) dp[v] = {0, 1}; for (int i : g[v]) { if (i == p) continue; dfs(i, v); if (dp[i].fr > dp[v].fr) { dp[v] = {dp[i].fr, 0}; } if (dp[i].fr == dp[v].fr) dp[v].se += dp[i].se; } dp[v].fr ++; } int main() { ll n; cin >> n; g.resize(n+7); for (int i = 0 ; i < n-1; i ++) { ll a, b; cin >> a >> b; g[a].pb(b); g[b].pb(a); } ll maxl = 0, res = 1; for (int i = 1; i <= n; i ++) { if (g[i].size() < 3) continue; dp.clear(); dp.resize(n+7, {0, 0}); dfs(i); vpll v; for (int j : g[i]) { v.pb({dp[j]}); } sort(v); ll cnt = 0; ll k = v.size(); if (v[k-1].fr == v[k-3].fr) { ll k1 = 0; for (int j = k-1; j >= 0; j --) { if (v[j].fr != v[k-1].fr) break; k1 += v[j].se; } for (int j = k-1; j >= 0; j --) { if (v[j].fr != v[k-1].fr) break; cnt += (k1-v[j].se)*(k1-v[j].se-1)/2; } } else if (v[k-1].fr == v[k-2].fr) { ll k1 = 0; for (int j = k-1; j >= 0; j --) { if (v[j].fr != v[k-3].fr) break; k1 += v[j].se; } cnt = k1+v[k-1].se+v[k-2].se; } else if (v[k-2].fr == v[k-3].fr) { ll k1 = 0; for (int j = k-2; j >= 0; j --) { if (v[j].fr != v[k-2].fr) break; k1 += v[j].se; } cnt = k1*(k1-1)/2; } else { ll k1 = 0; for (int j = k-1; j >= 0; j --) { if (v[j].fr != v[k-3].fr) break; k1 += v[j].se; } cnt = k1; } /*cout << i << endl; for (auto j : v) { cout << j.fr << ' ' << j.se << endl; }*/ if (v[k-1].fr*(v[k-2].fr+v[k-3].fr) > maxl) { maxl = v[k-1].fr*(v[k-2].fr+v[k-3].fr); res = 0; } if (v[k-1].fr*(v[k-2].fr+v[k-3].fr) == maxl) { res += cnt; } } cout << maxl << ' ' << res << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...