// #include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define pb push_back
#define F first
#define S second
const ll INF=1e9;
const int MAXN=1e5+100;
int n,m,l;
vector<vector<pair<int,int>>> v(MAXN);
vector<pair<ll,ll>> diameters;
bool visited[MAXN];
ll parr[MAXN];
ll depth[MAXN];
pair<ll,ll> dfs(int node,int par,ll ew=0){//depth, best node
if(visited[node]) return {ew,node};
visited[node]=true;
parr[node]=par;
depth[node]=ew;
// dbg(node,par,ew);
if(v[node].size()==1&&v[node][0].F==par){
return {ew,node};
}
ll ans=0;
ll best=node;
for(auto x:v[node]){
if(x.F!=par){
// dbg(x.F,node,ew,x.S);
pair<ll,ll> p=dfs(x.F,node,ew+x.S);
if(p.F>ans){
ans=p.F;
best=p.S;
}
}
}
return {ans,best};
}
ll bigdia=0;
int par[MAXN];
int f=0;
void find_diameter(int node){
memset(visited,false,sizeof(visited));
pair<ll,ll> p=dfs(node,node);
int f=p.S;
memset(parr,0,sizeof(parr));
memset(visited,false,sizeof(visited));
p=dfs(p.S,p.S);
// dbg(f,p.S);
vector<ll> dia;
while(p.S!=parr[p.S]) {
dia.push_back(p.S);
p.S=parr[p.S];
}
dia.push_back(p.S);
reverse(all(dia));
bigdia=p.F;
int nodea=0;
int nodeb=0;
int a,b,c,e;
ll besta=INF;
ll bestb=INF;
for(auto x:dia){
a=depth[dia.back()]-depth[x];
b=depth[x];
if(besta>max(a,b)){
besta=max(a,b);
nodea=x;
}
par[x]=dia[0];
}
// if(besta==INF){
// dbg(node);
// }
// assert(besta==INF);
diameters.pb({besta,nodea});
// dbg(besta,nodea);
// OVL(dia," ")
f++;
}
struct Edge{
ll a,b;
ll c;
bool operator < (const Edge& other) const{
return c<other.c;
}
};
int find(int node){
if(node==par[node]) return node;
return par[node]=find(par[node]);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n=N;
m=M;
l=L;
memset(visited,false,sizeof(visited));
for(int i=0;i<m;i++){
v[A[i]].push_back({B[i],T[i]});
v[B[i]].push_back({A[i],T[i]});
}
memset(depth,0,sizeof(depth));
for(int i=0;i<n;i++){
if(!visited[i]){
find_diameter(i);
}
}
vector<Edge> edges;
int d=diameters.size();
// cout<<d<<endl;
bool ok=true;
for(int i=0;i<n;i++){
ok&=(v[i].size()<=1);
}
// if(ok){
// for(int i=0;i<diameters.size();i++) dbg(diameters[i].F,diameters[i].S);
//answer of sub4 here
// for(int i=0;i+1<diameters.size();i++){
// v[diameters[i].S].push_back({diameters[i+1].S,l});
// v[diameters[i+1].S].push_back({diameters[i].S,l});
// dbg(diameters[i].S,diameters[i+1].S,l);
// }
// for(int i=0;i<n;i++) {
// cout<<i<<" --> ";
// for(auto x:v[i]){
// cout<<" [ "<<x.F<<" ; "<<x.S<<" ] ,";
// }
// cout<<endl;
// }
// memset(depth,0LL,sizeof(depth));
// dbg("START");
// find_diameter(0);
// dbg(f);
// return bigdia;
// }
for(int i=0;i<d-1;i++){
int nodea=diameters[i].S;
ll besta=diameters[i].F;
int nodeb=-1;
ll bestb=INF;
int j=i+1;
// dbg(nodea,besta);
// for(int j=i+1;j<d;j++){
// if(bestb>diameters[j].F){
// bestb=diameters[j].F;
// nodeb=diameters[j].S;
// }
// dbg(nodea,nodeb,besta,bestb);
edges.push_back({.a=nodea,.b=diameters[j].S,.c=besta+diameters[j].F});
// }
// dbg(nodea,nodeb);
}
sort(all(edges));
for(auto& edge:edges){
if(find(edge.a)==find(edge.b)) continue;
int a=find(edge.a);
int b=find(edge.b);
par[b]=a;
// dbg(edge.a,edge.b,edge.c);
// dbg(a,b,edge.a,edge.b);
v[edge.a].pb({edge.b,l});
v[edge.b].pb({edge.a,l});
f++;
}
// dbg(f);
memset(depth,0LL,sizeof(depth));
find_diameter(0);
//working for sub4
//here we have every element have at most one
return bigdia;
}
#ifdef IOI
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
#define MAX_N 100000
static int A[MAX_N];
static int B[MAX_N];
static int T[MAX_N];
int main() {
int N, M, L, i;
int res;
FILE *f = fopen("dreaming.in", "r");
if (!f)
fail("Failed to open input file.");
res = fscanf(f, "%d%d%d", &N, &M, &L);
for (i = 0; i < M; i++)
res = fscanf(f, "%d%d%d", &A[i], &B[i], &T[i]);
fclose(f);
int answer = travelTime(N, M, L, A, B, T);
printf("%d\n", answer);
return 0;
}
#endif
Compilation message
dreaming.cpp: In function 'void find_diameter(int)':
dreaming.cpp:64:9: warning: unused variable 'nodeb' [-Wunused-variable]
64 | int nodeb=0;
| ^~~~~
dreaming.cpp:65:13: warning: unused variable 'c' [-Wunused-variable]
65 | int a,b,c,e;
| ^
dreaming.cpp:65:15: warning: unused variable 'e' [-Wunused-variable]
65 | int a,b,c,e;
| ^
dreaming.cpp:67:8: warning: unused variable 'bestb' [-Wunused-variable]
67 | ll bestb=INF;
| ^~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:144:13: warning: unused variable 'nodeb' [-Wunused-variable]
144 | int nodeb=-1;
| ^~~~~
dreaming.cpp:145:12: warning: unused variable 'bestb' [-Wunused-variable]
145 | ll bestb=INF;
| ^~~~~
/usr/bin/ld: /tmp/ccJ0P5E3.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
