Submission #519849

#TimeUsernameProblemLanguageResultExecution timeMemory
519849Dasha_GnedkoHard route (IZhO17_road)C++17
19 / 100
2074 ms24048 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/detail/standard_policies.hpp> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //#pragma GCC optimize("Ofast") //#pragma GCC target("avx2") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4") using namespace std; //using namespace __gnu_pbds; //template <typename T> using ordered_set = tree <T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update>; mt19937 gen(time(0)); #define ll long long #define ld long double #define pb push_back #define F first #define S second #define TIME clock() * 1.0 / CLOCKS_PER_SEC #define sz(a) int32_t(a.size()) #define endl '\n' //#define int long long const int N = 1e6 + 100; const int M = 31; const int mod = 1e9 + 7; const int inf = 1e9 + 7; vector < int > g[N]; int leaf[N], ra[N]; int calc(int a, int b, int n) { vector < int > pr(n); for(int i = 0; i < n; i++) ra[i] = -1; ra[a] = 0; queue < int > q; q.push(a); while (!q.empty()) { int v = q.front(); q.pop(); for(auto to: g[v]) { if (ra[to] == -1) { ra[to] = ra[v] + 1; pr[to] = v; q.push(to); } } } int mx = ra[b]; while (1) { ra[b] = 0; q.push(b); if (b == a) break; b = pr[b]; } for(int i = 0; i < n; i++) if (ra[i] != 0) ra[i] = -1; while (!q.empty()) { int v = q.front(); q.pop(); for(auto to: g[v]) { if (ra[to] == -1) { ra[to] = ra[v] + 1; pr[to] = v; q.push(to); } } } int cnt = 0; for(int i = 0; i < n; i++) cnt = max(cnt, ra[i]); return cnt * mx; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #else // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); #endif // LOCAL int n; cin >> n; for(int i = 0; i < n - 1; i++) { int x, y; cin >> x >> y; x--; y--; g[x].pb(y); g[y].pb(x); } int mx = 0, k = 0; for(int i = 0; i < n; i++) leaf[i] = (sz(g[i]) == 1); for(int i = 0; i < n; i++) { if (!leaf[i]) continue; for(int j = i + 1; j < n; j++) { if (!leaf[j]) continue; int c = calc(i, j, n); if (c > mx) { mx = c; k = 1; } else if (c == mx) k++; } } cout << mx << " " << k; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...