| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 887015 | 2023-12-13T12:55:20 Z | BBart888 | Dreaming (IOI13_dreaming) | C++14 | 0 ms | 0 KB |
#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);
}
}
*/
int n, m, l;
vector<pair<int,ll>> adj[MAXN];
vector<int> cmp;
bool vis[MAXN];
ll dp[MAXN];
void dfs1(int v, int p)
{
vis[v] = true;
dp[v] = 0;
for (auto u : adj[v])
{
if (u.first == p)
continue;
dfs1(u.first, v);
dp[v] = max(dp[v], dp[u.first] + u.second);
}
}
int center;
ll dist;
void dfs2(int v, ll mx, int p)
{
ll mx1 = 0;
ll mx2 = 0;
int id = 0;
for (auto u : adj[v])
{
if (u.first == p)
continue;
ll x = dp[u.first] + u.second;
if (x > mx1)
{
mx2 = mx1;
mx1 = x;
id = u.first;
}
else if (x > mx2)
mx2 = x;
}
ll mxx = max(mx1,mx);
if (mxx < dist)
{
dist = mxx;
center = v;
}
for (auto u : adj[v])
{
if (u.first == p)
continue;
if (u.first == id)
swap(mx1, mx2);
dfs2(u.first, max(mx1, mx) + u.second, v);
if (u.first == id)
swap(mx1, mx2);
}
}
ll diam;
int diamv;
void dfs3(int v, ll L, int p)
{
if (L > diam)
{
diam = L;
diamv = v;
}
for (auto u : adj[v])
{
if (u.first != p)
dfs3(u.first, L + u.second, v);
}
}
vector<int> comp;
ll travelTime(int N, int M, int L, int a[], int b[], int t[])
{
n = N;
m = M;
l = L;
for (int i = 0; i < n; i++)
{
adj[a[i] + 1].push_back({ b[i] + 1 ,t[i]});
adj[b[i] + 1].push_back({ a[i] + 1 ,t[i]});
}
ll mx = 0;
int vert = 0;
for (int i = 1; i <= n; i++)
{
if (vis[i])
continue;
dist = 1e9;
center = i;
dfs1(i, i);
dfs2(i,0,i );
comp.push_back(center);
if (dist > mx)
{
mx = dist;
vert = comp.back();
}
}
for (auto v : comp)
{
if (v != vert)
{
adj[v].push_back({ vert,l });
adj[vert].push_back({ v,l });
}
}
dfs3(1, 0, 1);
dfs3(diamv, 0, diamv);
return diam;
}
/*
int main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(false);
//setIO("time");
return 0;
}
*/