Submission #399041

#TimeUsernameProblemLanguageResultExecution timeMemory
399041prvocisloDreaming (IOI13_dreaming)C++17
47 / 100
99 ms24768 KiB
#include <iostream> #include <vector> #include <algorithm> #include <set> #include <map> #include <bitset> #include"dreaming.h" typedef long long ll; using namespace std; const int maxn = 1e5 + 79, inf = 1e9 + 79; vector<int> vis(maxn, 0), dp(maxn, 0); vector<vector<pair<int, int> > > g(maxn); void dfs1(int u, int p) { vis[u] = 1; for (int i = 0; i < g[u].size(); i++) if (g[u][i].first == p) { g[u].erase(g[u].begin() + i); break; } for (pair<int, int> i : g[u]) { dfs1(i.first, u); dp[u] = max(dp[u], dp[i.first] + i.second); } } void dfs2(int u, int dist, int &mini, int &dia) { mini = min(mini, max(dist, dp[u])); vector<int> pf(g[u].size() + 1, 0), sf(g[u].size() + 1, 0); pair<int, int> p(0, 0); for (int i = 0; i < g[u].size(); i++) { int di = dp[g[u][i].first] + g[u][i].second; pf[i + 1] = max(pf[i], di); if (di > p.first) swap(p.first, p.second), p.first = di; else if (di > p.second) p.second = di; } dia = max({ dia, p.first + p.second, dp[u] + dist }); for (int i = g[u].size() - 1; i >= 0; i--) sf[i] = max(sf[i + 1], dp[g[u][i].first] + g[u][i].second); for (int i = 0; i < g[u].size(); i++) dfs2(g[u][i].first, max({ dist, pf[i], sf[i + 1] }) + g[u][i].second, mini, dia); } 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] }); vector<int> v; int ans = 0; for (int i = 0; i < n; i++) if (!vis[i]) { v.push_back(inf); dfs1(i, -1), dfs2(i, 0, v.back(), ans); } return max(v[0] + l + v[1], ans); }

Compilation message (stderr)

dreaming.cpp: In function 'void dfs1(int, int)':
dreaming.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for (int i = 0; i < g[u].size(); i++) if (g[u][i].first == p) { g[u].erase(g[u].begin() + i); break; }
      |                  ~~^~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int, int, int&, int&)':
dreaming.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for (int i = 0; i < g[u].size(); i++)
      |                  ~~^~~~~~~~~~~~~
dreaming.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for (int i = 0; i < g[u].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...