#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <cassert>
#include <cstring>
#include <climits>
#include <functional>
#include<cstdlib>
//#include "arc.h"
#include "dreaming.h"
using namespace std;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long LL;
const int MAXN = 2e5 + 11;
using ll = long long;
typedef vector<int> lnum;
const int base = 1e9;
const ll mod1 = 1e9 + 7;
const ll mod2 = 1000000021;
const ll P = 31;
/*
void setIO(string name = "") {
cin.tie(0)->sync_with_stdio(0); // see /general/fast-io
if ((name.size())) {
freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
freopen((name + ".out").c_str(), "w", stdout);
}
}
*/
ll dp[MAXN];
vector<pair<int,int>> adj[MAXN];
bool vis[MAXN];
vector<int> cmp;
int node;
vector<pair<ll, int>> vv;
int par[MAXN];
ll lon[MAXN];
void dfs1(int v, int p)
{
vis[v] = true;
cmp.push_back(v);
if (dp[v] > dp[node])
node = v;
for (auto u : adj[v])
{
if (u.first == p)
continue;
par[u.first] = v;
dp[u.first] = dp[v] + u.second;
dfs1(u.first, v);
}
}
void calc(int v, int p)
{
for (auto u : adj[v])
{
if (u.first == p)
continue;
calc(u.first, v);
lon[v] = max(lon[v], lon[u.first] + u.second);
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
for (int i = 0; i < m; i++)
{
adj[a[i] + 1].push_back({ b[i] + 1 ,t[i]});
adj[b[i] + 1].push_back({ a[i] + 1 ,t[i]});
}
for (int i = 1; i <= n; i++)
{
if (vis[i] == 0)
{
node = 0;
dfs1(i, -1);
for (int v : cmp)
dp[v] = 0,par[v] =0;
cmp.clear();
dfs1(node, -1);
int curr = node;
vector<int> path;
while (curr != 0)
{
path.push_back(curr);
curr = par[curr];
}
if (path.size() == 0)
path.push_back(i);
int sz = path.size();
int V = path[path.size() / 2];
calc(V, -1);
ll val1 = lon[V];
for (auto v : cmp)
lon[v] = 0;
V = path[(path.size() - 1) / 2];
calc(V, -1);
ll tmp = lon[V];
if (val1 < lon[V])
V = path[path.size() / 2];
val1 = min(val1, tmp);
vv.push_back({ val1,V });
cmp.clear();
}
}
sort(vv.rbegin(), vv.rend());
ll fin = vv[0].first;
for (int i = 1; i < vv.size(); i++)
{
fin = max(fin,vv[0].first + vv[i].first + l);
}
return fin;
}
/*
int main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(false);
//setIO("time");
return 0;
}
*/
Compilation message
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:121:8: warning: unused variable 'sz' [-Wunused-variable]
121 | int sz = path.size();
| ^~
dreaming.cpp:146:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for (int i = 1; i < vv.size(); i++)
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
20436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
20436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
13056 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
13008 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
20436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
