#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int lau;
stack<int> S;
vector<vector<pair<int,int>>> adjlist;
vector<int> maxin;
vector<int> maxout;
vector<int> visited;
int n,m;
void dfs(int node) {
S.push(node);
visited[node] = 1;
int maxmaxin=0;
for (pair<int,int> nei:adjlist[node]) {
if (visited[nei.first]) {
continue;
}
dfs(nei.first);
maxin[node] = max(maxin[node], maxin[nei.first]+nei.second); //maximum path from the node to any
//node in its subtree
}
}
void dfs2(int node) {
visited[node] = 1;
int maxmaxin=0;
vector<int> values;
vector<pair<int,int>> children;
int mout = maxout[node];
for (pair<int,int> nei:adjlist[node]) {
if (visited[nei.first]) {
continue;
}
children.push_back(nei);
values.push_back(nei.second+maxin[nei.first]);
}
int c=children.size();
vector<int> prefmax(c+1,0);
vector<int> suffmax(c+1,0);
for (int i=0; i<c; i++) {
prefmax[i+1] = max(prefmax[i], values[i]);
}
for (int i=c; i>=1; i--) {
suffmax[i-1] = max(suffmax[i], values[i-1]);
}
for (int i=0; i<c; i++) {
pair<int,int> nei=children[i];
if (visited[nei.first]) {
continue;
}
maxout[nei.first] = max(maxout[node],max(prefmax[i],suffmax[i+1]))+nei.second;
dfs2(nei.first);
}
}
signed travelTime(signed N, signed M, signed L, signed A[], signed B[], signed T[]) {
n=N;
m=M;
lau=L;
adjlist=vector<vector<pair<int,int>>>(N);
visited=vector<int>(N,0);
maxin=vector<int>(N,0);
maxout=vector<int>(N,0);
for (int i=0; i<M; i++) {
adjlist[A[i]].push_back({B[i],T[i]});
adjlist[B[i]].push_back({A[i],T[i]});
}
vector<vector<int>> conn;
for (int i=0; i<n; i++) {
if (!visited[i]) {
dfs(i);
vector<int> curcon;
while (S.size()) {
curcon.push_back(S.top());
S.pop();
}
conn.push_back(curcon);
}
}
visited=vector<int>(N,0);
for (int i=0; i<n; i++) {
if (!visited[i]) {
dfs2(i);
}
}
int c=conn.size();
int INF=1000000000007;
vector<int> weights(c,INF);
int k=0;
for (auto i:conn) {
for (auto j:i) {
weights[k]=min(weights[k],max(maxin[j],maxout[j]));
}
k++;
}
sort(weights.begin(), weights.end());
reverse(weights.begin(), weights.end());
/*for (auto i:weights) {
cout << i << " ";
}
cout << endl;*/
if (weights.size()==1) {
return weights[0];
}
else if (weights.size()==2) {
return weights[0]+weights[1]+L;
}
else {
assert(false);
return max(weights[1]+weights[2]+2*L, weights[0]+weights[1]+L);
}
}
Compilation message
dreaming.cpp: In function 'void dfs(long long int)':
dreaming.cpp:17:9: warning: unused variable 'maxmaxin' [-Wunused-variable]
17 | int maxmaxin=0;
| ^~~~~~~~
dreaming.cpp: In function 'void dfs2(long long int)':
dreaming.cpp:30:9: warning: unused variable 'maxmaxin' [-Wunused-variable]
30 | int maxmaxin=0;
| ^~~~~~~~
dreaming.cpp:33:9: warning: unused variable 'mout' [-Wunused-variable]
33 | int mout = maxout[node];
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
25648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
25648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
21908 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
25648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
