Submission #495229

#TimeUsernameProblemLanguageResultExecution timeMemory
495229KarliverHard route (IZhO17_road)C++17
0 / 100
10 ms12216 KiB
#include <bits/stdc++.h> #define FIXED_FLOAT(x) std::fixed <<std::setprecision(20) << (x) #define all(v) (v).begin(), (v).end() using namespace std; #define forn(i,n) for (int i = 0; i < (n); ++i) #define rforn(i, n) for(int i = (n) - 1;i >= 0;--i) #define sz(x) (int)x.size() #define ff first #define se second #define mp make_pair using ll = long long; int mod = (ll)1e9 + 7; const int INF = 1e9 + 1; const int N = 5e5 + 100; const double eps = 1e-7; template <class T> using V = vector<T>; template <class T> using VV = V<V<T>>; template<class T, size_t SZ> using AR = array<T, SZ>; template<class T> using PR = pair<T, T>; template <typename XPAX> bool ckma(XPAX &x, XPAX y) { return (x < y ? x = y, 1 : 0); } template <typename XPAX> bool ckmi(XPAX &x, XPAX y) { return (x > y ? x = y, 1 : 0); } V<int> g[N]; int dep[N]; PR<int> m1[N], m2[N]; int w[N]; map<ll, int> sp; void caldep(int v, int p) { for(auto c : g[v]) { if(c == p)continue; dep[c]= dep[v]+1; caldep(c, v); if(m1[c].ff+1 >m1[v].ff) { m1[v] = {m1[c].ff+1,c}; } else if(m1[c].ff+1 > m2[v].ff) { m2[v] = {m1[c].ff+1,c}; } } } void dfs1(int v, int p) { ckma(w[v], dep[v]); if(v != p) { ckma(w[v], (m1[p].se == v ? m2[p].ff : m1[p].ff)+1); ckma(w[v], w[p]+1); } for(auto c : g[v]) { if(c==p)continue; dfs1(c, v); } } void dfs2(int v,int p) { V<int> ds; for(auto c : g[v]) { if(c==p) { continue; } dfs2(c, v); ds.push_back(m1[c].ff+1); } sort(all(ds)); if(sz(ds)>=2 && v!= p) { int x = ds.back(), y = ds[sz(ds)-2]; ll mx = w[v]; ll cnt1 = count(all(ds), x), cnt2 = count(all(ds), y); ll ad = 0; if(x==y) ad = cnt1 * (cnt1-1)/2; else ad = cnt1*cnt2; ll lstsm = x+y; sp[mx*lstsm] += ad; } if(sz(ds) >= 3) { ll x = ds.back(), y = ds[sz(ds)-2], z = ds[sz(ds)-1]; ll lstsm = x+y; ll ad = 0; ll cnt1 = count(all(ds),x); ll cnt2 = count(all(ds),z); if(x==z) { ad = cnt1 * (cnt1 -1) / 2 * (cnt1-2); } else if(x==y) { ad = cnt2 * (cnt1-1)/2 * cnt2; } else ad = cnt2; sp[lstsm*ds[sz(ds)-3]] += ad; } } void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) void solve() { int n; cin >> n; forn(i, n -1) { int a, b; cin >> a >> b; --a;--b; g[a].push_back(b); g[b].push_back(a); } int root = 0; forn(i, n) { if(sz(g[i])>1) { root = i; break; } } caldep(root, root); dfs1(root, root); dfs2(root, root); debug(w[4]); if(!sz(sp)) sp[0]++; auto it = sp.rbegin(); //debug(sp); cout << it->first << ' ' << it->second << '\n'; } void test_case() { int t; cin >> t; forn(p, t) { //cout << "Case #" << p + 1 << ": "; solve(); } } int main() { ios::sync_with_stdio(false); cin.tie(0); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...