Submission #280149

#TimeUsernameProblemLanguageResultExecution timeMemory
280149KastandaDreaming (IOI13_dreaming)C++11
100 / 100
137 ms16920 KiB
// M #include<bits/stdc++.h> #include "dreaming.h" using namespace std; const int N = 100005; int n, m, L, D[3][N], M[N]; vector < pair < int , int > > Adj[N]; vector < int > vec; void DFS(int v, int p, int w) { M[v] = 1; if (w == 0) vec.push_back(v); for (auto u : Adj[v]) if (u.first != p) D[w][u.first] = D[w][v] + u.second, DFS(u.first, v, w); } int travelTime(int _n, int _m, int _L, int * A, int * B, int * W) { n = _n; m = _m; L = _L; for (int i = 0; i < m; i ++) { Adj[A[i]].push_back({B[i], W[i]}); Adj[B[i]].push_back({A[i], W[i]}); } int Mx = 0; vector < int > V; for (int i = 0; i < n; i ++) if (!M[i]) { vec.clear(); DFS(i, -1, 0); int d1 = i; for (int v : vec) if (D[0][v] > D[0][d1]) d1 = v; DFS(d1, -1, 1); int d2 = i; for (int v : vec) if (D[1][v] > D[1][d2]) d2 = v; DFS(d2, -1, 2); Mx = max(Mx, D[1][d2]); int Mn = D[1][d2]; for (int v : vec) Mn = min(Mn, max(D[1][v], D[2][v])); V.push_back(Mn); } sort(V.begin(), V.end()); reverse(V.begin(), V.end()); if ((int)V.size() > 1) Mx = max(Mx, V[0] + V[1] + L); if ((int)V.size() > 2) Mx = max(Mx, V[1] + V[2] + L * 2); return Mx; }
#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...