답안 #970662

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
970662 2024-04-27T03:33:41 Z yeediot 꿈 (IOI13_dreaming) C++17
컴파일 오류
0 ms 0 KB
#include<bits/stdc++.h>
//#include "dreaming.h"
using namespace std;
#define F first
#define S second
#define chmin(a,b) a=(a<b?a:b)
#define chmax(a,b) a=(a>b?a:b)
const int mxn=1e5+5;
vector<pair<int,int>>adj[mxn];
pair<int,int>dp[mxn];
bool vis[mxn];
int dp2[mxn];
void dfs(int v,int pa){
    vis[v]=1;
    for(auto [u,len]:adj[v]){
        if(u==pa)
            continue;
        dfs(u,v);
        if(dp[v].F<=dp[u].F+len){
            dp[v].S=dp[v].F;
            dp[v].F=dp[u].F+len;
        }
        else if(dp[v].S<dp[u].F+len){
            dp[v].S=dp[u].F+len;
        }
    }
}
pair<int,int> mn;
int mx=-2e9;
void reroot(int v,int pa){
    chmin(mn,make_pair(dp[v].F,v));
    for(auto [u,len]:adj[v]){
        if(u==pa)
            continue;
        int x;
        if(dp[v].F!=dp[u].F+len){
            x=dp[v].F;
        }
        else{
            x=dp[v].S;
        }
        x+=len;
        if(dp[u].F<=x){
            dp[u].S=dp[u].F;
            dp[u].F=x;
        }
        else if(dp[u].S<x){
            dp[u].S=x;
        }
        reroot(u,v);
    }
}
void dfs2(int v,int pa){
    for(auto [u,len]:adj[v]){
        if(u==pa)
            continue;
        dfs2(u,v);
        chmax(mx,dp2[v]+dp2[u]+len);
        chmax(dp2[v],dp2[u]+len);
    }
}
vector<pair<int,int>>v;
int travelTime(int n,int m,int l,int a[],int b[],int t[]){
    for(int i=0;i<m;i++){
        adj[a[i]].push_back({b[i],t[i]});
        adj[b[i]].push_back({a[i],t[i]});
    }
    for(int i=0;i<n;i++){
        if(vis[i])
            continue;
        mn={2e9,2e9};
        dfs(i,i);
        reroot(i,i);
        v.push_back(mn);
    }
    sort(v.begin(),v.end(),greater<pair<int,int>>());
    for(int i=1;i<(int)v.size();i++){
        adj[v[0].S].push_back({v[i].S,l});
        adj[v[i].S].push_back({v[0].S,l});
    }
    dfs2(0,0);
    return mx;
}
#ifdef local
int main(){
    freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);
    int n,m,l;
    cin>>n>>m>>l;
    int a[m],b[m],t[m];
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i]>>t[i];
    }
    cout<<travelTime(n,m,l,a,b,t)<<'\n';
}
#else
#endif

Compilation message

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