| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 416133 |
2021-06-02T05:03:52 Z |
DEQK |
Dreaming (IOI13_dreaming) |
C++17 |
|
0 ms |
0 KB |
#include "dreaming.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100100;
/*int travelTime(int n,int m,int l,vector<int> a,vector<int> b,vector<int> t) {
}*/
int n, m, l, ans;
int us[N], dp[N], was[N];
vector<pair<int, int>> g[N];
pair<int, int> best;
void dfs(int u) {
us[u] = 1;
for(auto to : g[u]) if(!us[to.first]) {
dfs(to.first);
dp[u] = max(dp[u], dp[to.first] + to.second);
}
}
void dfs2(int u,int val) {
was[u] = 1;
vector<int> p, s;
ans = max(ans, max(dp[u], val));
if(best.first > max(dp[u], val)) {
best = {max(dp[u], val), u};
}
for(int i = 0; i < g[u].size(); ++i) {
int to = g[u][i].first, c = g[u][i].second;
if(was[to]) continue;
p.push_back(!p.empty() ? max(p.back(), dp[to] + c) : dp[to] + c);
}
for(int i = g[u].size() - 1; i >= 0; i--) {
int to = g[u][i].first, c = g[u][i].second;
if(was[to]) continue;
s.push_back(s.empty() ? dp[to] + c : max(s.back(), dp[to] + c));
}
reverse(s.begin(), s.end());
for(int i = g[u].size() - 1; i >= 0; i--) {
int to = g[u][i].first, c = g[u][i].second;
if(was[to]) continue;
int f = val;
if(i) f = max(f, p[i - 1] );
if(i + 1 < s.size()) f = max(f, s[i + 1]);
dfs2(to, f + c);
}
}
int travelTime(int n,int m,int l,int a[],int b[],int t[]) {
for(int i = 0; i < m; ++i) {
int u = a[i],v = b[i],w = t[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
vector<pair<int, int>> d;
for(int i = 0; i < n; ++i) {
if(!us[i]) {
dfs(i);
best = {2e9, 0};
dfs2(i, 0);
d.push_back(best);
}
}
sort(d.begin(), d.end(), [&] (pair<int, int> &x, pair<int, int> &y) {
return x.first > y.first;
});
if(d.size() > 1) {
ans = max(ans, d[0].first + d[1].first + l);
}
if(d.size() > 2) {
ans = max(ans, dp[1].first + d[1].first + 2 * l);
}
return ans;
}
Compilation message
dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int i = 0; i < g[u].size(); ++i) {
| ~~^~~~~~~~~~~~~
dreaming.cpp:44:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | if(i + 1 < s.size()) f = max(f, s[i + 1]);
| ~~~~~~^~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:70:24: error: request for member 'first' in 'dp[1]', which is of non-class type 'int'
70 | ans = max(ans, dp[1].first + d[1].first + 2 * l);
| ^~~~~
