제출 #947347

#제출 시각아이디문제언어결과실행 시간메모리
947347gaga999Hard route (IZhO17_road)C++17
0 / 100
5 ms19900 KiB
#include <cstdio> #include <stdio.h> #include <iostream> #include <math.h> #include <vector> #include <queue> #include <stack> #include <deque> #include <algorithm> #include <utility> #include <set> #include <map> #include <stdlib.h> #include <cstring> #include <string.h> #include <string> #include <sstream> #include <assert.h> #include <climits> #include <sstream> #include <numeric> #include <time.h> #include <limits.h> #include <list> #include <bitset> #include <unordered_map> #include <unordered_set> #include <random> #include <iomanip> #include <complex> #include <chrono> #include <fstream> #include <functional> #include <unistd.h> // #pragma GCC optimize("Ofast,no-stack-protector") // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt") #define lowbit(x) ((x) & -(x)) #define ml(a, b) ((1ll * (a) * (b)) % M) #define tml(a, b) (a) = ((1ll * (a) * (b)) % M) #define ad(a, b) ((0ll + (a) + (b)) % M) #define tad(a, b) (a) = ((0ll + (a) + (b)) % M) #define mi(a, b) ((0ll + M + (a) - (b)) % M) #define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M) #define tmin(a, b) (a) = min((a), (b)) #define tmax(a, b) (a) = max((a), (b)) #define iter(a) (a).begin(), (a).end() #define riter(a) (a).rbegin(), (a).rend() #define init(a, b) memset((a), (b), sizeof(a)) #define cpy(a, b) memcpy((a), (b), sizeof(a)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define size(x) (int)x.size() #define pb emplace_back #define mpr make_pair #define ls(i) ((i) << 1) #define rs(i) ((i) << 1 | 1) #define INF 0x3f3f3f3f #define NIF 0xc0c0c0c0 #define eps 1e-9 #define F first #define S second #define int long long #define AC cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long llt; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef pair<llt, llt> pll; typedef complex<double> cd; // const int M = 998244353; // random_device rm; // mt19937 rg(rm()); // default_random_engine rg(rm()); // uniform_int_distribution<int> rd(INT_MIN, INT_MAX); // uniform_real_distribution<double> rd(0, M_PI); void db() { cerr << "\n"; } template <class T, class... U> void db(T a, U... b) { cerr << a << " ", db(b...); } inline char gc() { const static int SZ = 1 << 16; static char buf[SZ], *p1, *p2; if (p1 == p2 && (p2 = buf + fread(p1 = buf, 1, SZ, stdin), p1 == p2)) return -1; return *p1++; } void rd() {} template <typename T, typename... U> void rd(T &x, U &...y) { x = 0; bool f = 0; char c = gc(); while (!isdigit(c)) f ^= !(c ^ 45), c = gc(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = gc(); f && (x = -x), rd(y...); } template <typename T> void prt(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) prt(x / 10); putchar((x % 10) ^ 48); } const int N = 5e5 + 5; vector<int> eg[N]; llt ans = 0, num = 1; struct A { int mx, nm; A() : mx(0), nm(1) {} void operator+=(const A &rh) { if (rh.mx == mx) nm += rh.nm; else if (rh.mx > mx) *this = rh; } } dp[N]; struct P { A v0, v1, v2; P() { v0.mx = v1.mx = v2.mx = -INF; } void add(A v) { if (v.mx > v0.mx) swap(v, v0); if (v.mx > v1.mx) swap(v, v1); if (v.mx > v2.mx) swap(v, v2); else if (v.mx == v2.mx) v2.nm += v.nm; } inline llt gv() { return (0ll + v0.mx) * (v1.mx + v2.mx); } inline llt gn() { if (v0.mx == v1.mx && v1.mx == v2.mx) return ((v1.nm + v2.nm + v0.nm - 1) * (v1.nm + v2.nm + v0.nm)) >> 1; if (v0.mx == v1.mx) return (0ll + v2.nm) * (v0.nm + v1.nm); if (v1.mx == v2.mx) return ((v1.nm + v2.nm - 1) * (v1.nm + v2.nm)) >> 1; return v2.nm; } }; void dfs(int u, int fa) { for (int v : eg[u]) { if (v == fa) continue; dfs(v, u); dp[u] += dp[v]; } dp[u].mx++; } void slv(int u, int fa) { A mx, sc; P cr; sc.mx = -INF; for (int v : eg[u]) { cr.add(dp[v]); if (dp[v].mx == mx.mx) mx.nm += dp[v].nm; else { if (dp[v].mx > mx.mx) sc += mx, mx = dp[v]; else sc += dp[v]; } } llt vv = cr.gv(), nn = cr.gn(); if (vv == ans) num += nn; else if (vv > ans) ans = vv, num = nn; A pr = dp[u]; for (int v : eg[u]) { if (v == fa) continue; if (dp[v].mx == mx.mx) { if (dp[v].nm == mx.nm) dp[u] = sc; else dp[u] = mx, dp[u].nm -= dp[v].nm; } else dp[u] = mx; dp[u].mx++; slv(v, u); } dp[u] = pr; } signed main() { int n, x, y; rd(n); for (int i = 1; i < n; i++) { rd(x, y); eg[x].pb(y); eg[y].pb(x); } dfs(1, -1), slv(1, -1); if (!ans) assert(num == 1); assert(num <= n * (llt)n); prt(ans), putchar(' '); prt(num), putchar('\n'); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...