Submission #1073768

#TimeUsernameProblemLanguageResultExecution timeMemory
1073768andrewpDreaming (IOI13_dreaming)C++14
77 / 100
1064 ms16476 KiB
//Dedicated to my love, ivaziva #include <bits/stdc++.h> #include "dreaming.h" using namespace std; using pii = pair<int, int>; using ll = int64_t; #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define dbg(x) cerr << #x << ": " << x << '\n'; constexpr int mxN = 1e5 + 20; vector<pii> g[mxN]; int dist1[mxN], dist2[mxN], par[mxN]; int dist3[mxN], dist4[mxN]; bool vis[mxN]; vector<int> vec, dijametar; vector<pii> vv; void dfs(int x, int p) { vis[x] = true; vec.push_back(x); for (auto ptr: g[x]) { if (ptr.first != p) { dist1[ptr.first] = dist1[x] + ptr.second; dfs(ptr.first, x); } } } void dfs2(int x, int p) { par[x] = p; for (auto ptr: g[x]) { if (ptr.first != p) { dist2[ptr.first] = dist2[x] + ptr.second; dfs2(ptr.first, x); } } } void dfs3(int x, int p) { for (auto ptr: g[x]) { if (ptr.first != p) { dist2[ptr.first] = dist2[x] + ptr.second; dfs3(ptr.first, x); } } } void dfs4(int x, int p) { for (auto ptr: g[x]) { if (ptr.first != p) { dist3[ptr.first] = dist3[x] + ptr.second; dfs4(ptr.first, x); } } } int travelTime(int N, int M, int L, int* A, int* B, int* T) { for (int i = 0; i < M; i++) { g[A[i]].push_back({B[i], T[i]}); g[B[i]].push_back({A[i], T[i]}); } for (int i = 0; i < N; i++) { dist1[i] = 0, dist2[i] = 0; vis[i] = false; } int ans = 0; vector<int> diams, anss; for (int i = 0; i < N; i++) { if (!vis[i]) { dijametar.clear(); vec.clear(); dfs(i, -1); int mx = 0, root = 0; for (int x: vec) { if (mx < dist1[x]) { root = x; mx = dist1[x]; } } dfs2(root, -1); int diamend = 0; mx = -1; for (int x: vec) { if (mx < dist2[x]) { mx = dist2[x]; diamend = x; } } while (diamend != -1) { dijametar.push_back(diamend); diamend = par[diamend]; } int diff = (int)(2e9), cen = 0, krc = 0; for (int x: dijametar) { if (diff > abs(mx - 2 * dist2[x])) { diff = abs(mx - 2 * dist2[x]); cen = x; krc = dist2[x]; } } ans = max(ans, mx); vv.push_back(make_pair(max(krc, mx - krc), cen)); } } sort(rall(vv)); for (int i = 1; i < vv.size(); i++) { ans = max(ans, vv[0].first + vv[i].first + L); } if (vv.size() >= 3) { ans = max(ans, vv[1].first + 2 * L + vv[2].first); } return ans; } /*int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cerr.tie(nullptr); int n, m, l; cin >> n >> m >> l; int a[m], b[m], t[m]; for (int i = 0; i < m; i++) { cin >> a[i] >> b[i] >> t[i]; } int ans = travelTime(n, m, l, a, b, t); cout << ans << '\n'; return 0; }*/ /* 12 8 2 0 8 4 8 2 2 2 7 4 5 11 3 5 1 7 1 3 1 1 9 5 10 6 3 */

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:108:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for (int i = 1; i < vv.size(); i++) {
      |                     ~~^~~~~~~~~~~
#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...