// created 01 FEB 2018
// updated JUNE 2018
// updated JULY 2018
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
#include <map>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <bitset>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <list>
#include <stdexcept>
using namespace std;
vector<vector<int> > adjlist;
vector<vector<int> > adjlist_weight;
vector<int> comps;
vector<int> depth;
vector<int> depth1;
int label(int v, int c) {
if(comps[v]!=-1) return 0;
comps[v]=c;
for(int i=0;i<adjlist[v].size();i++) {
label(adjlist[v][i],c);
}
return 1;
}
int label_dist(int v, int d) {
if(depth[v]!=-1) return 0;
depth[v]=d;
for(int i=0;i<adjlist[v].size();i++) {
label_dist(adjlist[v][i],d+adjlist_weight[v][i]);
}
return 1;
}
int label_dist1(int v, int d) {
if(depth1[v]!=-1) return 0;
depth1[v]=d;
for(int i=0;i<adjlist[v].size();i++) {
label_dist1(adjlist[v][i],d+adjlist_weight[v][i]);
}
return 1;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<int> temp;
adjlist.clear();
adjlist_weight.clear();
for(int i=0;i<N;i++) {
temp.clear();
adjlist.push_back(temp);
adjlist_weight.push_back(temp);
comps.push_back(-1);
}
for(int i=0;i<M;i++) {
adjlist[A[i]].push_back(B[i]);
adjlist[B[i]].push_back(A[i]);
adjlist_weight[A[i]].push_back(T[i]);
adjlist_weight[B[i]].push_back(T[i]);
}
/*for(int i=0;i<N;i++) {
cout << i << ": ";
for(int j=0;j<adjlist[i].size();j++) {
cout << adjlist[i][j] << " ";
}
cout << endl;
}*/
/*vector<pair<int,int> > leaf; //first is weight, second is i
pair<int,int> p;
for(int i=0;i<N;i++) {
if(adjlist[i].size()==1) {
p.first=adjlist_weight[i][0];
p.second=i;
leaf.push_back(p);
}
if(adjlist[i].size()==0) {
p.first=0;
p.second=i;
leaf.push_back(p);
}
}
sort(leaf.begin(),leaf.end());
for(int i=0;i<leaf.size();i++) {
cout << "leaf is at " << leaf[i].second << endl;
}*/
int c=0;
for(int v=0;v<N;v++) {
if(label(v,c)==1) c++;
}
/*for(int i=0;i<N;i++) {
cout << i << ": " << comps[i] << endl;
}*/
vector<int> center(c);
vector<int> center1(c);
vector<int> hba(N,0); //is 1 if i has been added at some point in past
vector<queue<int> > bfs;
queue<int> ttemp;
//if(not ttemp.empty()) cout << "WHAT";
for(int i=0;i<c;i++) bfs.push_back(ttemp);
for(int i=0;i<N;i++) {
if(adjlist[i].size()==1 or adjlist[i].size()==0) {
bfs[comps[i]].push(i);
hba[i]=1;
}
}
//cout << bfs[0].front() << endl;
//now we do bfs
int k=-10;
for(int i=0;i<c;i++) {
ttemp=bfs[i];
k=-10;
//cout << ttemp.front() << endl;
while(ttemp.size()>1) {
k=ttemp.front();
ttemp.pop();
for(int j=0;j<adjlist[k].size();j++) {
if(hba[adjlist[k][j]]==1) continue;
hba[adjlist[k][j]]=1;
ttemp.push(adjlist[k][j]);
}
}
center[i]=ttemp.front();
if(k!=-10) center1[i]=k;
else center1[i]=ttemp.front();
}
/*for(int i=0;i<c;i++) {
cout << "color " << i << " has center " << center[i] << endl;
}*/
//now we find radii
vector<int> radii(c,0);
vector<int> radii1(c,0);
vector<int> far(c);
for(int i=0;i<N;i++) {
depth.push_back(-1);
}
for(int i=0;i<c;i++) {
label_dist(center[i],0);
}
for(int i=0;i<N;i++) {
if(depth[i]>radii[comps[i]]) {
radii[comps[i]]=depth[i];
far[comps[i]]=i;
}
}
for(int i=0;i<N;i++) {
depth1.push_back(-1);
}
for(int i=0;i<c;i++) {
label_dist1(center1[i],0);
}
for(int i=0;i<N;i++) {
if(depth1[i]>radii1[comps[i]]) radii1[comps[i]]=depth1[i];
}
/*for(int i=0;i<N;i++) {
cout << i << ": depth = " << comps[i] << endl;
}*/
/*for(int i=0;i<c;i++) {
cout << "color " << i << " has radius " << radii[i] << endl;
}*/
/*for(int i=0;i<c;i++) {
cout << "color " << i << " has radius " << radii1[i] << endl;
}*/
for(int i=0;i<c;i++) {
radii[i]=min(radii[i],radii1[i]);
}
/*for(int i=0;i<c;i++) {
cout << "color " << i << " has radius " << radii[i] << endl;
}*/
vector<int> diam(c,0);
depth1.clear();
for(int i=0;i<N;i++) {
depth1.push_back(-1);
}
for(int i=0;i<c;i++) {
label_dist1(far[i],0);
}
for(int i=0;i<N;i++) {
if(depth1[i]>diam[comps[i]]) diam[comps[i]]=depth1[i];
}
/*for(int i=0;i<c;i++) {
cout << "color " << i << " has diam " << diam[i] << endl;
}*/
int maxdiam=0;
for(int i=0;i<c;i++) {
if(diam[i]>maxdiam) maxdiam=diam[i];
}
sort(radii.begin(),radii.end());
if(c==1) return maxdiam;
if(c==2) {
return max(maxdiam,radii[c-1]+radii[c-2]+L);
}
if(c>=3) {
int tempans=max(maxdiam,radii[c-1]+radii[c-2]+L);
return max(tempans,2*L+radii[c-2]+radii[c-3]);
}
return 42;
}
Compilation message
dreaming.cpp: In function 'int label(int, int)':
dreaming.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adjlist[v].size();i++) {
~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int label_dist(int, int)':
dreaming.cpp:45:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adjlist[v].size();i++) {
~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int label_dist1(int, int)':
dreaming.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adjlist[v].size();i++) {
~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:139:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<adjlist[k].size();j++) {
~^~~~~~~~~~~~~~~~~~
/tmp/ccdxVe5h.o: In function `main':
grader.c:(.text.startup+0xa2): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
