Submission #1263287

#TimeUsernameProblemLanguageResultExecution timeMemory
1263287aren_danceDreaming (IOI13_dreaming)C++20
10 / 100
54 ms22336 KiB
#include <iostream> #include <vector> #include <set> #include <algorithm> #include "dreaming.h" using namespace std; const int N = 3e5+1; vector<pair<int, int>> g[N]; int dp[N]; int depth[N]; int mx[N]; bool vis[N]; vector<int> gag[2]; int o; vector<pair<int,int>> hert; void dfs2(int v,int p) { mx[v] = depth[v]; for (auto i : g[v]) { if (i.first == p) { continue; } depth[i.first] = depth[v] + i.second; dfs2(i.first,v); mx[v] = max(mx[i.first], mx[v]); } dp[v] = mx[v] - depth[v]; vector<int> mas; for (auto i : g[v]) { if (i.first == p) { continue; } mas.push_back(mx[i.first]); } if (mas.empty() || mas.size()==1) { return; } sort(mas.rbegin(), mas.rend()); dp[v] = max(dp[v],mas[0] + mas[1] - 2*depth[v]); } int get() { for (int i = 0;i < o;++i) { dp[i] = 0; mx[i] = 0; depth[i] = 0; } dfs2(0,-1); int answ = 0; for (int i = 0;i < o;++i) { answ = max(answ, dp[i]); } return answ; } void dfs(int v,int comp) { vis[v] = 1; gag[comp].push_back(v); for (auto i : g[v]) { if (!vis[i.first]) { dfs(i.first, comp); } } } void dfs3(int v,int p,int dep) { hert.push_back({v, dep }); for (auto i:g[v]) { if (i.first == p) { continue; } dfs3(i.first, v, dep + i.second); } } int travelTime(int n, int m, int l, int a[], int b[], int t[]) { o = n; 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] }); } int cnt = 0; for (int i = 0;i < n;++i) { if (!vis[i]) { dfs(i, cnt); ++cnt; } } if (n <= 100) { int answ = 1e9; for (auto i : gag[0]) { for (auto j : gag[1]) { g[i].push_back({ j,l }); g[j].push_back({ i,l }); int p = get(); answ = min(answ, p); g[i].pop_back(); g[j].pop_back(); } } return answ; } int p1 = 1; for (auto i : gag[0]) { if (g[i].size() == 1) { p1 = i; break; } } dfs3(p1, -1, 0); int mn = 0; int answ = 1e9; for (auto i : hert) { int h = max(i.second, hert.back().second - i.second); if (answ > h) { answ = h; mn = i.first; } } hert.clear(); for (auto i : gag[0]) { if (g[i].size() == 1) { p1 = i; break; } } dfs3(p1, -1, 0); int mn2 = 0; answ = 1e9; for (auto i : hert) { int h = max(i.second, hert.back().second- i.second); if (answ > h) { answ = h; mn2 = i.first; } } g[mn].push_back({ mn2,l }); g[mn2].push_back({ mn,l }); return get(); }
#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...