#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("VNOICUP.INP");
ofstream fout("VNOICUP.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#include <stdio.h>
#include <stdlib.h>
#include "dreaming.h"
const int mxn = 1e5 + 5;
vt<pii>adj[mxn + 1];
ll dp[mxn + 1], dp2[mxn + 1];
bool vis[mxn + 1];
vt<int>comp;
void dfs(int s, int pre){
comp.pb(s);
vis[s] = 1; dp[s] = 0;
bool leaf = 1;
for(auto [i, w]: adj[s]){
if(i != pre){
dfs(i, s);
dp[s] = max(dp[s], dp[i] + w);
leaf = 0;
}
}
}
void dfs2(int s, int pre){
ll p = dp2[s];
for(auto [i, w]: adj[s]){
if(i != pre){
dp2[i] = max(dp2[i], p + w);
p = max(p, dp[i] + w);
}
}
reverse(adj[s].begin(), adj[s].end());
p = dp2[s];
for(auto [i, w]: adj[s]){
if(i != pre){
dp2[i] = max(dp2[i], p + w);
p = max(p, dp[i] + w);
}
}
for(auto [i, w]: adj[s]){
if(i != pre){
dfs2(i, s);
}
}
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
forr(i, 0, m){
int u = A[i], v = B[i], w = T[i];
adj[u].pb({v, w}); adj[v].pb({u, w});
}
ll ans = 0;
forr(i, 1, n + 1){
if(!vis[i]){
comp.clear();
dfs(i, -1);
dfs2(i, -1);
ll res = 1e18;
for(auto j: comp){
res = min(res, max(dp[j], dp2[j]));
}
ans += res;
}
}
ans += L;
return(ans);
}
/*
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
#define MAX_N 100000
static int A[MAX_N];
static int B[MAX_N];
static int T[MAX_N];
int main() {
int N, M, L, i;
int res;
/*
FILE *f = fopen("dreaming.in", "r");
if (!f)
fail("Failed to open input file.");
res = scanf("%d%d%d", &N, &M, &L);
for (i = 0; i < M; i++)
res = scanf("%d%d%d", &A[i], &B[i], &T[i]);
int answer = travelTime(N, M, L, A, B, T);
printf("%d\n", answer);
return 0;
}
*/
Compilation message
dreaming.cpp:97:5: warning: "/*" within comment [-Wcomment]
97 | /*
|
dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:30:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
30 | for(auto [i, w]: adj[s]){
| ^
dreaming.cpp:29:10: warning: variable 'leaf' set but not used [-Wunused-but-set-variable]
29 | bool leaf = 1;
| ^~~~
dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
41 | for(auto [i, w]: adj[s]){
| ^
dreaming.cpp:49:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
49 | for(auto [i, w]: adj[s]){
| ^
dreaming.cpp:55:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
55 | for(auto [i, w]: adj[s]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
15216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
15216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
6868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
15216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
