Submission #1074153

#TimeUsernameProblemLanguageResultExecution timeMemory
1074153TrumlingDreaming (IOI13_dreaming)C++14
14 / 100
65 ms15800 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]; bool vis[mxN]; vector<int> vec, dijametar; 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); } } } 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; } 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 = 0; for (int x: vec) { if (mx < dist2[x]) { mx = dist2[x]; diamend = x; } } diams.push_back(mx); 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(dist2[x] - (mx - dist2[x]) )) { diff = abs(dist2[x] - (mx - dist2[x]) ); cen = x; krc = dist2[x]; } } anss.push_back(max(krc, mx - krc)); } } int ans = max(diams[0], diams[1]); ans = max(ans, anss[0] + anss[1] + L); return ans; }

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:75:36: warning: variable 'cen' set but not used [-Wunused-but-set-variable]
   75 |             int diff = (int)(2e9), cen = 0, krc = 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...