| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 111789 | 2019-05-16T07:27:50 Z | CodeKracker | Dreaming (IOI13_dreaming) | C++14 | 0 ms | 0 KB |
/*input
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/
/**
Author: Kristopher Paul
Date Created: 16-05-2019
Contest Name:
_/ _/ _/_/_/_/ _/ _/_/_/_/
_/ _/ _/ _/ _/ _/
_/_/ _/_/_/_/ _/ _/_/_/_/
_/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/_/_/_/
**/
#include "dreaming.h"
#include<bits/stdc++.h>
#define ll long long
//#define int ll
#define pb push_back
#define INF 0x3f3f3f3f //0x3f3f3f3f = 63
#define MOD 1000000009
#define mp make_pair
const double PI=3.141592653589793238462643383279502884197169399375105820974944;
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define umap unordered_map
#define pii pair<int,int>
#define F first
#define S second
#define mii map<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define itr :: iterator it
#define all(v) v.begin(),v.end()
#define WL(t) while(t--)
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define out(x) cout << #x << " is " << x << endl
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
ll ModExp(ll x,ll y,ll m){
ll res = 1;
x = x % m;
while (y > 0)
{
if (y & 1)
res = (res*x) % m;
y = y>>1;
x = (x*x) % m;
}
return res;
}
vector<pair<ll,ll> > adj[100005];
bool vis[100005] = {};
ll mxdist = 0;
int node = 0;
void dfs(int cv,int par,ll cdist){
vis[cv] = true;
FOR(i,0,adj[cv].size()){
if(adj[cv][i].first != par){
dfs(adj[cv][i].first,cv,adj[cv][i].second+cdist);
}
}
if(cdist > mxdist){
mxdist = cdist;
node = cv;
}
}
vector<pair<ll,ll> > path;
bool f = false;
void fpath(int cv,int par,ll cdist){
path.pb({cv,cdist});
FOR(i,0,adj[cv].size()){
if(adj[cv][i].first != par){
fpath(adj[cv][i].first,cv,cdist+adj[cv][i].second);
}
if(f){
return;
}
}
if(cdist == mxdist){
f = true;
return;
}
if(f){
return;
}
path.pop_back();
}
ll center(int cv){
mxdist = 0;
node = cv;
dfs(cv,-1,0);
int ncv = node;
mxdist = 0;
node = cv;
dfs(ncv,-1,0);
f = false;
path.clear();
fpath(ncv,-1,0);
ll ecc = 1e18;
ll tot = path[path.size()-1].second;
FOR(i,0,path.size()){
ll a = path[i].second;
ll b = tot-a;
remin(ecc,max(a,b));
}
return ecc;
}
ll travelTime(int n,int m,int l,int a[],int b[],int t[]){
FOR(i,0,m){
adj[a[i]].pb({b[i],t[i]});
adj[b[i]].pb({a[i],t[i]});
}
vector<ll> ecc;
FOR(i,0,n){
if(!vis[i]){
ll val = center(i);
ecc.pb(val);
}
}
sort(ecc.rbegin(),ecc.rend());
if(ecc.size() == 1){
return ecc[0];
}else if(ecc.size() == 2){
return ecc[0]+l+ecc[1];
}else{
return max(ecc[1]+ecc[2]+(2*l),ecc[0]+l+ecc[1]);
}
}
/*
void solve(){
int n,m,l;
cin >> n >> m >> l;
int a[m],b[m],t[m];
FOR(i,0,m){
cin >> a[i] >> b[i] >> t[i];
}
cout << travelTime(n,m,l,a,b,t) << endl;
}
signed main(){
FastIO;
int t = 1;
// cin >> t;
WL(t){
solve();
}
}
*/