Submission #703833

#TimeUsernameProblemLanguageResultExecution timeMemory
703833Chal1shkanParkovi (COCI22_parkovi)C++14
0 / 110
66 ms26996 KiB
# include <bits/stdc++.h> # define pb push_back # define ff first # define ss second # define nl "\n" # define sz(x) ((int)(x).size()) # define deb(x) cerr << #x << " = " << x << endl; # define pll pair <ll, ll> typedef long long ll; typedef unsigned long long ull; typedef long double ld; const ll maxn = 2e5 + 25; const ll inf = 1e18 + 0; const ll mod = 1e9 + 7; const ll dx[] = {-1, 1, 0, 0}; const ll dy[] = {0, 0, -1, 1}; using namespace std; ll n, k, ans; vector <pll> g[maxn]; ll sz[maxn]; void dfs_calc (ll v, ll pa) { sz[v] = 1; for (auto i : g[v]) { ll to = i.ff; if (to == pa) continue; dfs_calc(to, v); sz[v] += sz[to]; } } ll find_c (ll v, ll pa, ll siz) { for (auto i : g[v]) { ll to = i.ff; if (to == pa) continue; if (sz[to] + sz[to] > siz) { return find_c(to, v, siz); } } return v; } void dfs_mx(ll v, ll pa, ll d) { ans = max(ans, d); for (auto i : g[v]) { ll to = i.ff, w = i.ss; if (to == pa) continue; dfs_mx(to, v, d + w); } } void ma1n (/* SABR */) { cin >> n >> k; for (ll i = 1, u, v, w; i < n; ++i) { cin >> u >> v >> w; g[u].pb({v, w}); g[v].pb({u, w}); } if (k == 1) { dfs_calc(1, 1); ll cen = find_c(1, 1, sz[1]); dfs_mx(cen, cen, 0); cout << ans << nl << cen << nl; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("file.in", "r", stdin); // freopen("file.out", "w", stdout); int ttt = 1; // cin >> ttt; for (int test = 1; test <= ttt; ++test) { // cout << "Case " << test << ":" << ' '; ma1n(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...