Submission #947568

#TimeUsernameProblemLanguageResultExecution timeMemory
947568PringHard route (IZhO17_road)C++17
100 / 100
527 ms92344 KiB
#include <bits/stdc++.h> using namespace std; #ifdef MIKU string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m"; #define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x) void dout() { cout << dbrs << endl; } template <typename T, typename ...U> void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); } #else #define debug(...) 39 #endif #define int long long #define fs first #define sc second #define mp make_pair #define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++) typedef pair<int, int> pii; const int MXN = 500005; int n; vector<int> edge[MXN]; pii d[MXN], u[MXN]; int pnt[MXN]; pii operator+(pii a, pii b) { if (a < b) swap(a, b); if (a.fs == b.fs) a.sc += b.sc; return a; } int SUM(vector<int> &v) { int ans = 0; for (auto &i : v) ans += i; return ans; } struct P { pii a, b; void init() { a = mp(0LL, 0LL); b = mp(0LL, 0LL); } void PUSH(pii x) { if (x.fs > a.fs) { b = a; a = x; } else if (x.fs == a.fs) { a.sc += x.sc; } else if (x.fs > b.fs) { b = x; } else if (x.fs == b.fs) { b.sc += x.sc; } } pii GET(pii x) { if (x.fs != a.fs) return a; if (x.sc == a.sc) return b; return mp(a.fs, a.sc - x.sc); } } p[MXN]; bool chain() { int big = 0; FOR(i, 1, n + 1) big = max(big, (int) edge[i].size()); return big <= 2; } void DFS1(int id, int par) { pnt[id] = par; d[id] = mp(0LL, 1LL); for (auto &i : edge[id]) { if (i == par) continue; DFS1(i, id); d[id] = d[id] + mp(d[i].fs + 1, d[i].sc); } } void DFS2(int id, int par) { u[id] = p[par].GET(mp(d[id].fs + 1, d[id].sc)); u[id].fs++; p[id].init(); p[id].PUSH(u[id]); for (auto &i : edge[id]) { if (i == par) continue; p[id].PUSH(mp(d[i].fs + 1, d[i].sc)); } for (auto &i : edge[id]) { if (i == par) continue; DFS2(i, id); } } pii calc(int id) { if (edge[id].size() < 3) return mp(0LL, 0LL); vector<int> c(3, -1); vector<vector<int>> v(3); c[0] = u[id].fs; v[0].push_back(u[id].sc); for (auto &i : edge[id]) { if (i == pnt[id]) continue; debug(d[i].fs + 1, d[i].sc); bool f = false; FOR(j, 0, 3) if (d[i].fs + 1 == c[j]) { v[j].push_back(d[i].sc); f = true; break; } if (f) continue; FOR(j, 0, 3) if (d[i].fs + 1 > c[j]) { c.insert(c.begin() + j, d[i].fs + 1); v.insert(v.begin() + j, vector<int>(1, d[i].sc)); break; } if (c.size() == 4) { c.pop_back(); v.pop_back(); } } if (v[0].size() >= 3) { int x = 2 * c[0] * c[0]; int s = SUM(v[0]), y = 0; for (auto &i : v[0]) y += i * (s - i); return mp(x, y / 2); } if (v[0].size() == 2) { int x = c[0] * (c[0] + c[1]); return mp(x, (v[0][0] + v[0][1]) * SUM(v[1])); } if (v[1].size() >= 2) { int x = 2 * c[0] * c[1]; int s = SUM(v[1]), y = 0; for (auto &i : v[1]) y += i * (s - i); return mp(x, y / 2); } return mp(c[0] * (c[1] + c[2]), v[1][0] * SUM(v[2])); } void miku() { int x, y; cin >> n; FOR(i, 1, n) { cin >> x >> y; edge[x].push_back(y); edge[y].push_back(x); } if (chain()) { cout << "0 1" << '\n'; return; } int rt = [&]() -> int { FOR(i, 1, n + 1) if (edge[i].size() == 1) return i; return 0; }(); DFS1(rt, 0); p[rt].init(); p[rt].PUSH(mp(0LL, 1LL)); for (auto &i : edge[rt]) p[rt].PUSH(mp(d[i].fs + 1, d[i].sc)); for (auto &i : edge[rt]) DFS2(i, rt); debug(rt); FOR(i, 1, n + 1) debug(i, u[i].fs, u[i].sc); pii ans = mp(0LL, 0LL); FOR(i, 1, n + 1) { // ans = ans + calc(i); pii x = calc(i); debug(i, x.fs, x.sc); ans = ans + x; } cout << ans.fs << ' ' << ans.sc << '\n'; } int32_t main() { cin.tie(0) -> sync_with_stdio(false); cin.exceptions(cin.failbit); miku(); return 0; }

Compilation message (stderr)

road.cpp: In function 'pii calc(long long int)':
road.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
road.cpp:103:9: note: in expansion of macro 'debug'
  103 |         debug(d[i].fs + 1, d[i].sc);
      |         ^~~~~
road.cpp: In function 'void miku()':
road.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
road.cpp:161:5: note: in expansion of macro 'debug'
  161 |     debug(rt);
      |     ^~~~~
road.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
road.cpp:162:22: note: in expansion of macro 'debug'
  162 |     FOR(i, 1, n + 1) debug(i, u[i].fs, u[i].sc);
      |                      ^~~~~
road.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
road.cpp:167:9: note: in expansion of macro 'debug'
  167 |         debug(i, x.fs, x.sc);
      |         ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...