Submission #900549

#TimeUsernameProblemLanguageResultExecution timeMemory
900549gun_ganDreaming (IOI13_dreaming)C++17
18 / 100
31 ms13788 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MX = 1e5 + 5; int N, M, L; vector<pair<int,int>> g[MX]; bool vis[MX]; int cur = 0, mx = 0, z = 0, len = 0; vector<int> vec; int p = 0, q = 0; pair<int,int> par[MX]; void dfs(int v) { vis[v] = 1; vec.push_back(v); if(cur > mx) { mx = cur; z = v; } for(auto [u, w] : g[v]) { if(!vis[u]) { if(cur + w > len / 2 && !p && len > 0) { p = cur; q = len - cur; } cur += w; par[u] = {v, w}; dfs(u); cur -= w; } } } vector<pair<int,int>> P; 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 = 1; i <= N; i++) { if(vis[i]) continue; vec.clear(); cur = 0, mx = 0, z = 0, len = 0, p = 0, q = 0; dfs(i); for(auto x : vec) { vis[x] = 0; par[x] = {z, 0}; } if(vec.size() == 1) { for(auto x : vec) { vis[x] = 1; } P.push_back({0, 0}); continue; } if(vec.size() == 2) { for(auto x : vec) { vis[x] = 1; } P.push_back({mx, 0}); continue; } vec.clear(); int tz = z; cur = 0, mx = 0, z = 0; dfs(tz); len = mx; int k = z, sum = 0, y = 2e9; while(k != tz) { if(abs((sum) - (len - sum)) < y) { y = abs((sum) - (len - sum)); p = sum; q = len - sum; } sum += par[k].second; k = par[k].first; } vec.clear(); P.push_back({max(p, q), min(p, q)}); } sort(P.rbegin(), P.rend()); int ans = 0; for(auto [x, y] : P) { ans = max(ans, x + y); } if(P.size() > 1) { ans = max(ans, P[0].first + L + P[1].first); } if(P.size() > 2) { ans = max(ans, P[1].first + 2 * L + P[2].first); } return ans; } /* int aa[100], bb[100], cc[100]; int main() { aa[0] = 1, bb[0] = 2, cc[0] = 2; aa[1] = 2, bb[1] = 3, cc[1] = 3; aa[2] = 4, bb[2] = 5, cc[2] = 3; aa[3] = 5, bb[3] = 6, cc[3] = 2; cout << travelTime(6, 4, 2, aa, bb, cc) << '\n'; } */
#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...