#include <bits/stdc++.h> #define rep(i, a, b) for (int i = (a); i < (b); i++) #define per(i, a, b) for(int i = (a); i > (b); i--) #define ll long long #define pb push_back #define xx first #define yy second #define pb push_back #define pii pair<int,int> #define vi vector<int> #define vpii vector<pii> using namespace std; constexpr bool DEG = 0; #define DEBUG if(DEG) constexpr int N = 1e5+7; vpii graf[N]; int par[N], odl[N],drugi, R; pii sred[N]; int n,m,l; int Find(int v){ if(par[v] == v) return v; return par[v] = Find(par[v]); } void Union(int a, int b){ a = Find(a); b = Find(b); if(a == b) return; par[b] = a; pii w1 = {sred[a].xx + l, sred[b].xx}; if(w1.xx < w1.yy) swap(w1.xx, w1.yy); pii w2 = {sred[a].xx, sred[b].xx + l}; if(w2.xx < w2.yy) swap(w2.xx, w2.yy); if(w1.xx > w2.xx) w1 = w2; else if(w1.xx == w2.xx) w1.yy = min(w1.yy, w2.yy); pii s1 = sred[a]; pii s2 = sred[b]; if(s1.xx < s2.xx) s1 = s2; else if(s1.xx == s2.xx) s1.yy = max(s1.yy, s2.yy); if(w1.xx > s1.xx) s1 = w1; else if(w1.xx == s1.xx) s1.yy = max(s1.yy, w1.yy); sred[a] = s1; } int dfs(int v, int p = -1){ if(p == -1) odl[v] = 0; int maxx = v; for(auto i : graf[v]){ if(i.yy == p) continue; odl[i.yy] = odl[v] + i.xx; int c = dfs(i.yy, v); if(odl[maxx] < odl[c]){ maxx = c; } Union(v,i.yy); } return maxx; } int dfs2(int v, int p = -1){ int czy = (v == drugi); for(auto i : graf[v]){ if(i.yy == p) continue; czy |= dfs2(i.yy, v); } if(czy == 0) return 0; pii xd = {odl[drugi] - odl[v], odl[v]}; if(xd.xx < xd.yy) swap(xd.xx, xd.yy); if(xd.xx < sred[R].xx){ sred[R] = xd; } return 1; } int travelTime(int N,int M,int L, vi A, vi B, vi T){ n = N; m = M; l = L; rep(i,0,m){ graf[A[i]].pb({T[i], B[i]}); graf[B[i]].pb({T[i], A[i]}); } rep(v,0,n) par[v] = v, odl[v] = -1; rep(i,0,n){ if(odl[i] == -1){ int c = dfs(i); drugi = dfs(c); R = Find(i); sred[R] = {odl[drugi], 0}; dfs2(c); } } rep(i,0,n-1) Union(i,i+1); int w = Find(1); int wynik = sred[w].xx + sred[w].yy; return wynik; } /* int main(){ int n1,m1,l1; cin>>n1>>m1>>l1; vi a,b,c; rep(i,0,m1){ int x,y,z; cin>>x>>y>>z; a.pb(x); b.pb(y); c.pb(z); } cout<<travelTime(n1,m1,l1,a,b,c)<<"\n"; } 12 8 2 0 1 4 1 2 2 2 3 4 5 6 3 6 7 7 7 8 5 9 10 3 11 7 1 */

/usr/bin/ld: /tmp/ccPjrWqX.o: in function `main':
grader.c:(.text.startup+0xc5): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status