제출 #1287664

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

dreaming

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
bool vis[maxn];
vector<pair<int, int>> adj[maxn];
int comp[maxn];
int cnt;

struct NODE{
    int max1, max2, id1, id2;
    inline NODE(){
        max1 = max2 = id1 = id2 = -1;
    }
} node[maxn];

void DFS(int u, int p){
    vis[u] = true;
    node[u].max1 = 0; node[u].id1 = u;
    for (auto [v, w] : adj[u]) if (v != p){
        DFS(v, u);
        if (node[v].max1 + w >= node[u].max1){
            node[u].max2 = node[u].max1;
            node[u].id2 = node[u].id1;
            node[u].max1 = node[v].max1 + w;
            node[u].id1 = v;
        }
        else if (node[v].max1 + w > node[u].max2){
            node[u].max2 = node[v].max1 + w;
            node[u].id2 = v;
        }
    }
    // cout << u << ' ' << node[u].max1 << ' ' << node[u].max2 << '\n';
    return;
}

int solve(int u, int p, int pre_len){
    int res = max(pre_len, node[u].max1);
    for (auto [v, w] : adj[u]) if (v != p){
        int down = pre_len + w;
        if (v != node[u].id1){
            down = max(down, node[u].max1 + w);
            res = min(res, solve(v, u, down));
        }
        else{
            down = max(down, node[u].max2 + w);
            res = min(res, solve(v, u, down));
        }
    }
    return res;
}

pair<int, int> parameter(int u, int p){
    pair<int, int> res = {0, u};
    for (auto [v, w] : adj[u]) if (v != p){
        pair<int, int> d = parameter(v, u);
        if (d.first + w > res.first)
            res.first = d.first + w, res.second = d.second;
    }
    return res;
}

int travelTime(int n, int m, int L, int a[], int b[], int t[]){
    int ans = 0;
    memset(vis, false, sizeof(vis));    
    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]){
        DFS(i, -1);
        comp[cnt] = solve(i, -1, 0); 
        pair<int, int> d = parameter(i, -1);
        d = parameter(d.second, -1);
        ans = max(ans, d.first);
        cnt++;
    }
    sort(comp, comp + cnt);
    int cur = comp[cnt - 1];
    for (int i = 0; i < cnt - 1; ++i){
        ans = max(ans, L + cur + comp[i]);
        cur = max(max(cur, comp[i]), min(cur, comp[i]) + L);
    }
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int a[] = {0,8,2,5,5,1,1,10};
    int b[] = {8,2,7,11,1,3,9,6};
    int t[] = {4,2,4,3,7,1,5,3};
    cout << travelTime(12, 8, 2, a, b, t);
}

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

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