#include "dreaming.h"
# include <bits/stdc++.h>
# define ll long long
# define fi first
# define se second
using namespace std;
// idenya dfs dua kali
// yang pertama subtree normal, yang kedua dari luar subtree
vector< pair<int, int> > edge[100001];
bool vis[100001];
int ins[100001];
vector<int> pref[100001], suff[100001];
void dfs(int a, int pr) {
vis[a] = 1;
ins[a] = 0;
for(int k=0;k<edge[a].size();k++) {
if(edge[a][k].fi == pr) continue;
dfs(edge[a][k].fi, a);
ins[a] = max(ins[edge[a][k].fi] + edge[a][k].se, ins[a]);
}
}
int cek;
void fn(int a, int pr, int bf) {
// cout<<"a : "<<a<<" "<<bf<<" "<<ins[a]<<endl;
cek = min(cek, max(bf, ins[a]));
pref[a].resize(edge[a].size());
suff[a].resize(edge[a].size());
for(int k=0;k<edge[a].size();k++) {
if(edge[a][k].fi == pr) {
if(k == 0) pref[a][k] = 0;
else pref[a][k] = pref[a][k - 1];
} else {
if(k == 0) pref[a][k] = ins[edge[a][k].fi] + edge[a][k].se;
else pref[a][k] = max(pref[a][k-1], ins[edge[a][k].fi] + edge[a][k].se);
}
}
for(int k=edge[a].size() - 1;k>=0;k--) {
if(edge[a][k].fi == pr) {
if(k == edge[a].size() - 1) suff[a][k] = 0;
else suff[a][k] = suff[a][k + 1];
} else {
if(k == edge[a].size() - 1) suff[a][k] = ins[edge[a][k].fi] + edge[a][k].se;
else suff[a][k] = max(suff[a][k+1], ins[edge[a][k].fi] + edge[a][k].se);
}
}
for(int k=0;k<edge[a].size();k++) {
if(edge[a][k].fi == pr) continue;
int mx = 0;
if(k > 0) mx = max(mx, pref[a][k - 1]);
if(k + 1 < edge[a].size()) mx = max(mx, suff[a][k + 1]);
// cout<<"AA : "<<edge[a][k].fi<<" "<<mx<<" "<<edge[a][k].se<<endl;
fn(edge[a][k].fi, a, max(mx, bf) + edge[a][k].se);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int k=0;k<N;k++) {
edge[k].clear();
vis[k] = 0;
}
for(int i=0;i<M;i++) {
edge[A[i]].push_back(make_pair(B[i], 1ll * T[i]));
edge[B[i]].push_back(make_pair(A[i], 1ll * T[i]));
}
vector<int> P;
P.clear();
for(int i=0;i<N;i++) {
if(!vis[i]) {
cek = 2e9;
dfs(i, -1);
fn(i, -1, 0);
P.push_back(cek);
// cout<<ins[i]<<endl;
cout<<i<<" "<<cek<<endl;
}
}
sort(P.begin(), P.end());
if(P.size() == 1) return P[0];
else if(P.size() == 2) return P[0] + P[1] + L;
else {
int t1 = P.back() + L + P[P.size() - 2];
int t2 = P[P.size() - 2] + L + P[P.size() - 3];
return max(t1, t2);
}
}
Compilation message
dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:18:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(int k=0;k<edge[a].size();k++) {
| ~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'void fn(int, int, int)':
dreaming.cpp:32:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int k=0;k<edge[a].size();k++) {
| ~^~~~~~~~~~~~~~~
dreaming.cpp:43:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | if(k == edge[a].size() - 1) suff[a][k] = 0;
| ~~^~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:46:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | if(k == edge[a].size() - 1) suff[a][k] = ins[edge[a][k].fi] + edge[a][k].se;
| ~~^~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int k=0;k<edge[a].size();k++) {
| ~^~~~~~~~~~~~~~~
dreaming.cpp:56:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | if(k + 1 < edge[a].size()) mx = max(mx, suff[a][k + 1]);
| ~~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
23376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
23376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
15200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
23376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
