/*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();
}
pair<ll,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));
}
pair<ll,ll> tmp = {ecc,mxdist};
return tmp;
}
int 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<pair<ll,ll> > ecc;
FOR(i,0,n){
if(!vis[i]){
pair<ll,ll> val = center(i);
ecc.pb(val);
}
}
sort(ecc.rbegin(),ecc.rend());
if(ecc.size() == 1){
return ecc[0].second;
}else if(ecc.size() == 2){
return ecc[0].first+l+ecc[1].first;
}else{
return max(ecc[1].first+ecc[2].first+(2*l),ecc[0].first+l+ecc[1].first);
}
}
/*
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();
}
}
*/
Compilation message
dreaming.cpp: In function 'void dfs(int, int, long long int)':
dreaming.cpp:32:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,a,b) for (int i = a; i < b; i++)
dreaming.cpp:75:9:
FOR(i,0,adj[cv].size()){
~~~~~~~~~~~~~~~~~~
dreaming.cpp:75:5: note: in expansion of macro 'FOR'
FOR(i,0,adj[cv].size()){
^~~
dreaming.cpp: In function 'void fpath(int, int, long long int)':
dreaming.cpp:32:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,a,b) for (int i = a; i < b; i++)
dreaming.cpp:91:9:
FOR(i,0,adj[cv].size()){
~~~~~~~~~~~~~~~~~~
dreaming.cpp:91:5: note: in expansion of macro 'FOR'
FOR(i,0,adj[cv].size()){
^~~
dreaming.cpp: In function 'std::pair<long long int, long long int> center(int)':
dreaming.cpp:32:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,a,b) for (int i = a; i < b; i++)
dreaming.cpp:122:9:
FOR(i,0,path.size()){
~~~~~~~~~~~~~~~
dreaming.cpp:122:5: note: in expansion of macro 'FOR'
FOR(i,0,path.size()){
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
74 ms |
16872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
74 ms |
16872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
74 ms |
16872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
6236 KB |
Output is correct |
| 2 |
Correct |
28 ms |
6240 KB |
Output is correct |
| 3 |
Correct |
32 ms |
6240 KB |
Output is correct |
| 4 |
Correct |
31 ms |
6268 KB |
Output is correct |
| 5 |
Correct |
31 ms |
6268 KB |
Output is correct |
| 6 |
Correct |
31 ms |
7464 KB |
Output is correct |
| 7 |
Correct |
28 ms |
6388 KB |
Output is correct |
| 8 |
Correct |
27 ms |
6268 KB |
Output is correct |
| 9 |
Correct |
28 ms |
6264 KB |
Output is correct |
| 10 |
Correct |
32 ms |
6384 KB |
Output is correct |
| 11 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 12 |
Correct |
11 ms |
4980 KB |
Output is correct |
| 13 |
Correct |
12 ms |
4980 KB |
Output is correct |
| 14 |
Correct |
11 ms |
4980 KB |
Output is correct |
| 15 |
Correct |
10 ms |
4980 KB |
Output is correct |
| 16 |
Correct |
11 ms |
4980 KB |
Output is correct |
| 17 |
Correct |
11 ms |
4980 KB |
Output is correct |
| 18 |
Correct |
12 ms |
5108 KB |
Output is correct |
| 19 |
Correct |
11 ms |
4980 KB |
Output is correct |
| 20 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 21 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 22 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 23 |
Correct |
11 ms |
4980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
74 ms |
16872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
74 ms |
16872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
