제출 #1336234

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1336234		paskalisapo	꿈 (IOI13_dreaming)	C++20	컴파일 에러	0 ms	0 KiB

dreaming

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 1;

vector<vector<pair<int,int>>> adj;
vector<bool> visited;
vector<int> maxdist1;
vector<int> maxdist2;
vector<int> parnode;
int n , m , l;
int curmindist;
int tempans = 0;


void dfs1(int cur) {
    visited[cur] = true;
    for(auto &x : adj[cur]) {
        if(visited[x.first]){
            parnode[cur] = x.second;
            continue;
        }
        dfs1(x.first);
        if(maxdist1[cur] < maxdist1[x.first] + x.second){
            maxdist2[cur] = maxdist1[cur];
            maxdist1[cur] =maxdist1[x.first] + x.second;
        }
        else if(maxdist2[cur] < maxdist1[x.first] + x.second) {
            maxdist2[cur] = maxdist1[x.first] + x.second;
        }
    }
    tempans = max(tempans, maxdist1[cur] + maxdist2[cur]);
}

//rerouting
void dfs2(int cur,int par){
    if(par != -1) {
        int tocomp = maxdist1[par] + parnode[cur];
        if(maxdist1[cur] + parnode[cur] == maxdist1[par]) {
            tocomp = maxdist2[par] + parnode[cur];
        }
        if(maxdist1[cur] < tocomp){
            maxdist2[cur] = maxdist1[cur] ;
            maxdist1[cur] = tocomp;
        }
        else if(maxdist2[cur] < tocomp){
            maxdist2[cur] = tocomp;
        }
    }
    for(auto &x : adj[cur]) {
        if(x.first == par){
            continue;
        }
        dfs2(x.first, cur);
    }
    curmindist = min(curmindist, maxdist1[cur]);
}


int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    adj.resize(N);
    visited.resize(N);
    maxdist1.resize(N);
    maxdist2.resize(N);
    parnode.resize(N);
    for(int i = 0;i < M ;i++) {
        adj[A[i]].push_back(pair(B[i], T[i]));
        adj[B[i]].push_back(pair(A[i], T[i]));
    }
    n = N;
    m =  M;
    l = L;


    vector<int> v;
    for(int i = 0; i < N ; i++) {
        if(!visited[i]) {
            curmindist = INF;
            dfs1(i);
            dfs2(i, -1);
            v.push_back(curmindist);
        }
    }

    sort(v.rbegin(), v.rend());
    int l = (N - 1)/ 2;
    int r = l + 1;
    int ind = 0;
    int maxright = 0;
    int maxleft = 0;
    int ans = 0;
    while(ind < v.size()) {
        ans = max(ans, maxleft + v[ind]);
        maxright =max(maxright, v[ind] + (r - l) * L);
        l--;
        ind++;
        if(ind < v.size()) {
            ans = max(ans , maxright + v[ind]);
            maxleft = max(maxleft, v[ind] + (r - l) * L);
            r++;
            ind++;
        }
    }
    //check biggest diameter of a component
    ans = max(ans, tempans);

    return ans;
}

int main() {
    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) << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

/usr/bin/ld: /tmp/cc98qxdk.o: in function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'; /tmp/ccU0QsMI.o:dreaming.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc98qxdk.o: in function `main':
grader.c:(.text.startup+0xc5): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status