Submission #2869905
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define TRACE(x) x #define WATCH(x) TRACE(cout << #x" = " << x << endl) #define WATCHR(a, b) TRACE(for (auto it=a; it!=b;) cout << *(it++) << " "; cout << endl) #define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end());}) #define all(x) (x).begin(), (x).end() typedef long long ll; typedef vector<bool> vb; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ll> vll; typedef vector<vll> vvll; void calc_depths(vvi &tree, int loc, int par, int dep, vi &mc) { int nc = 0; for (int nbr : tree[loc]) { if (nbr != par) { nc++; calc_depths(tree, nbr, loc, dep+1, mc); } } if (nc) { while (mc.size() <= dep) mc.push_back(0); mc[dep] = max(mc[dep], nc); } } int main() { ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); cout << fixed << setprecision(15); int N; cin >> N; vvi tree(N); for (int i = 0; i < N - 1; i++) { int u, v; cin >> u >> v; tree[u-1].push_back(v-1); tree[v-1].push_back(u-1); } int md = INT_MAX; vvi depths(N); for (int i = 0; i < N; i++) { calc_depths(tree, i, i, 0, depths[i]); md = min(md, (int) depths[i].size()); } vi centers; for (int i = 0; i < N; i++) { if (depths[i].size() == md) centers.push_back(i); } if (centers.size() == 2) { vi mc1; calc_depths(tree, centers[0], centers[1], 0, mc1); vi mc2; calc_depths(tree, centers[1], centers[0], 0, mc2); ll ans = 2; for (int i = 0; i < mc1.size(); i++) ans = ans * max(mc1[i], mc2[i]); cout << mc1.size() + 1 << " " << ans << endl; return 0; } // case that we just use the center as the root vi mc; calc_depths(tree, centers[0], centers[0], 0, mc); int col = mc.size() + 1; ll ans = 1; for (int v : mc) ans *= v; // try making a neighbor the second center for (int nbr : tree[centers[0]]) { vi mc1; calc_depths(tree, centers[0], nbr, 0, mc1); vi mc2; calc_depths(tree, nbr, centers[0], 0, mc2); while (mc1.size() < mc2.size()) mc1.push_back(0); while (mc2.size() < mc1.size()) mc2.push_back(0); ll cand = 2; for (int i = 0; i < mc1.size(); i++) cand *= max(mc1[i], mc2[i]); if (mc1.size() + 1 < col) { col = mc1.size() + 1; ans = cand; } else if (mc1.size() + 1 == col) { ans = min(ans, cand); } } cout << col << " " << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Isomorphism Freak |
User | socketnaut |
Language | C++14 (Clang 3.8.0) |
Score | 0 |
Code Size | 2731 Byte |
Status | CE |
Compile Error
./Main.cpp:1:10: fatal error: 'bits/stdc++.h' file not found #include <bits/stdc++.h> ^ 1 error generated.