| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 488908 | ssense | Dreaming (IOI13_dreaming) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "dreaming.h"
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define nax 200005
#define pb push_back
#define sc second
#define fr first
//#define int unsigned long long
//#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
vector<vector<pair<int, int>> adj;
int bfs(int s)
{
queue<pair<pair<int, int>, int>> q;
q.push({{s, -1}, 0});
int now = 0;
while(!q.empty())
{
int node = q.front().fr.fr;
int dist = q.front().sc;
int parent = q.front().fr.sc;
now = max(now, dist);
q.pop();
for(auto v : adj[node])
{
if(v.fr != parent)
{
q.push({{v.fr, node}, dist+v.sc});
}
}
}
return now;
}
bool vis[105];
int dfs(int u, int par)
{
int ans = bfs(u);
vis[u] = true;
for(auto v : adj[u])
{
if(v.fr != par)
{
ans = min(ans, dfs(v.fr, u));
}
}
return ans;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
adj.clear();
for(int i = 0; i < n; i++)
{
vector<pair<int, int>> cop;
adj.pb(cop);
vis[i] = false;
}
for(int i = 0; i < m; i++)
{
adj[a[i]].pb({b[i], t[i]});
adj[b[i]].pb({a[i], t[i]});
}
int ans = 0;
vint mx;
for(int i = 0; i < n; i++)
{
if(!vis[i])
{
mx.pb(dfs(i, -1));
}
}
assert(mx.size() == 2);
sort(all(mx));
ans+=mx[mx.size()-1];
ans+=mx[mx.size()-2];
ans+=l;
return ans;
}
/*
int main()
{
int n, m, l;
cin >> n >> m >> l;
int a[m], b[m], t[m];
for(int i = 0; i < m; i++)
{
cin >> a[i] >> b[i] >> t[i];
}
cout << travelTime(n, m, l, a, b, t) << endl;
}
*/
/*
7
5
2
0 1 10
0 5 5
5 4 6
3 2 2
2 6 1
8 6 3
0 1 1
1 2 1
1 3 1
1 4 10
4 5 10
6 7 7
2 0 2
3 1 10
1 2 1
*/