Submission #124429

#TimeUsernameProblemLanguageResultExecution timeMemory
124429khulegubDreaming (IOI13_dreaming)C++14
0 / 100
35 ms3832 KiB
#include "dreaming.h" #include <bits/stdc++.h> #define mp make_pair #define xx first #define yy second #define pb push_back using namespace std; typedef long long i64; typedef pair<int, int> pii; //don't forget to change the array sizes vector<vector<pair<int, int> > > to; int n; int m; int l; bool vis[100010]; int dia, h; int h1[100010], h2[100010]; void mark(int u){ vis[u] = 1; for (pii vw : to[u]){ int v = vw.xx; if (!vis[v]){ mark(v); } } } void dosz(int u, int pre){ int mx1 = 0, mx2 = 0; for (pii vw : to[u]){ int v = vw.xx; if (v != pre){ dosz(v, u); if (mx1 < h1[v] + vw.yy){ mx2 = mx1; mx1 = h1[v] + vw.yy; } else if (mx2 < h1[v] + vw.yy) mx2 = h1[v] + vw.yy; } } h1[u] = mx1; h2[u] = mx2; } void crawl(int u, int pre){ h = min(h, max(h1[u], h2[u])); dia = max(dia, h1[u]); for (pii vw : to[u]){ int v = vw.xx; if (v != pre){ int tmpu1 = h1[u], tmpv1 = h1[v]; int tmpu2 = h2[u], tmpv2 = h2[v]; if (h1[u] == vw.yy + h1[v]){ //take the second h1[u] = h2[u]; } if (h1[u] + vw.yy > h1[v]){ h2[v] = h1[v]; h1[v] = h1[u] + vw.yy; } else if (h1[u] + vw.yy > h2[v]) h2[v] = h1[u] + vw.yy; crawl(v, u); h1[v] = tmpv1, h2[v] = tmpv2; h1[u] = tmpu1, h2[u] = tmpu2; } } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { n = N, m = M, l = L; for (int i = 0; i < m; i++){ to[A[i]].pb(mp(B[i], T[i]) ); to[B[i]].pb(mp(A[i], T[i]) ); } vector<int> hs; int ans = 0; for (int i = 0; i < n; i++){ if (!vis[i]){ h = 1e9; dia = 0; dosz(i, i); crawl(i, i); ans = max(dia, ans); //ans could be diametr of one subtree hs.pb(h); mark(i); } } sort(hs.rbegin(), hs.rend()); if (hs.size() > 1){ // 2 or more trees ans = max(ans, hs[0] + hs[1] + l); } if (hs.size() > 2){ // three or more trees ans = max(ans, hs[1] + hs[2] + 2*l); } // cout << ans; return ans; } // int dfs2(int ) // int main(){ // freopen("in.txt", "r", stdin); // cin >> n >> m >> l; // to.resize(n); // for (int i = 0, a, b, t; i < m; i++){ // cin >> a >> b >> t; // to[a].pb(mp(b, t)); // to[b].pb(mp(a, t)); // } // } //don't forget to change the array sizes
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...