Submission #92539

#TimeUsernameProblemLanguageResultExecution timeMemory
92539Just_Solve_The_ProblemHard route (IZhO17_road)C++11
52 / 100
1031 ms88796 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int N = (int)5e5 + 7; int n; pair < int, int > refresh(pair < int, int > A, pair < int, int > B) { if (A.first < B.first) { return B; } else if (A.first > B.first) { return A; } else { return {A.first, A.second + B.second}; } } struct T { pair < int, int > tree[4 * N]; T() { } void upd(int pos, int val, int v = 1, int l = 1, int r = n) { if (l == r) { tree[v] = {val, 1}; return ; } int mid = (l + r) >> 1; if (pos <= mid) { upd(pos, val, v + v, l, mid); } else { upd(pos, val, v + v + 1, mid + 1, r); } tree[v] = refresh(tree[v + v], tree[v + v + 1]); } pair < int, int > getmax(int l, int r, int v = 1, int tl = 1, int tr = n) { if (tl > r || tr < l) return {0, 0}; if (l <= tl && tr <= r) return tree[v]; int mid = (tl + tr) >> 1; return refresh(getmax(l, r, v + v, tl, mid), getmax(l, r, v + v + 1, mid + 1, tr)); } }; T tr; vector < int > gr[N]; int tin[N], tout[N], tiktak; int h[N]; pair < ll, ll > ans, ans1; pair < int, int > asd; void dfs(int v, int pr) { tin[v] = ++tiktak; tr.upd(tin[v], h[v]); for (int to : gr[v]) { if (to == pr) continue; h[to] = h[v] + 1; dfs(to, v); } tout[v] = tiktak; } void dfs1(int v, int pr, pair < int, int > mxx, pair < int, int > asd) { pair < int, int > fir, sec; for (int to : gr[v]) { if (to == pr) continue; pair < int, int > res = mxx; pair < int, int > asd1 = asd; fir = tr.getmax(tin[to], tout[to]); sec = refresh(tr.getmax(tin[v] + 1, tin[to] - 1), tr.getmax(tout[to] + 1, tout[v])); sec.first -= h[v]; fir.first -= h[v]; if (mxx.first > 0) { if (sec.first > 0) { if ((fir.first + sec.first) * 1LL * mxx.first > ans.first) { ans.first = (fir.first + sec.first) * 1LL * mxx.first; ans.second = fir.second * 1LL * sec.second; } else if ((fir.first + sec.first) * 1LL * mxx.first == ans.first) { ans.second += fir.second * 1LL * sec.second; } if ((fir.first + mxx.first) * 1LL * sec.first > ans1.first) { ans1.first = (fir.first + mxx.first) * 1LL * sec.first; ans1.second = fir.second * 1LL * mxx.second; asd1.first = h[v] + fir.first; asd1.second = mxx.second; } else if ((fir.first + mxx.first) * 1LL * sec.first == ans1.first) { if (fir.first + h[v] == asd1.first) { ans1.second += fir.second * 1LL * (mxx.second - asd1.second); } else { ans1.second += fir.second * 1LL * mxx.second; asd1.first = fir.first + h[v]; } asd1.second = mxx.second; } } } if (res.first < sec.first) { asd1.second = 0; } res = refresh(res, sec); res.first++; dfs1(to, v, res, asd1); } } main() { //freopen("road.in", "r", stdin); //freopen("road.out", "w", stdout); scanf("%d", &n); for (int i = 1; i < n; i++) { int u, v; scanf("%d %d", &u, &v); gr[u].push_back(v); gr[v].push_back(u); } ans = ans1 = {0, 1}; dfs(1, 1); dfs1(1, 1, {0, 1}, {-1, 0}); ans.second /= 2; ans = refresh(ans, ans1); cout << ans.first << ' ' << ans.second; } /* 8 1 2 2 3 3 4 2 5 5 6 6 8 5 7 */

Compilation message (stderr)

road.cpp:108:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
road.cpp: In function 'int main()':
road.cpp:111:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
road.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...