제출 #1180894

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

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)

unordered_map<int, vector<pair<int, int>>> adjList;
bool vis[100005];
int d1[100005];
int d2[100005];

void dp1(vector<int> &comp, vector<int> &leaves, int v, int p = -1) {

    comp.push_back(v);
    d1[v] = 0;

    int mxp1 = -1, mxp2 = -1;

    for(auto i : adjList[v]) if(i.first != p) {
        dp1(comp, leaves, i.first, v);
        int pl = d1[i.first] + i.second;
        d1[v] = max(d1[v], pl);
        if(mxp1 < pl) {
            mxp2 = mxp1;
            mxp1 = pl;
        } else if (mxp2 < pl) mxp2 = pl;
    }

    if(mxp2 != -1) {
        d2[v] = mxp1+mxp2;
    }
    if(mxp1 != -1) leaves.push_back(v);
}

pair<int, int> solve(int r) {
    vector<int> connComp;
    vector<int> leaves;

    dp1(connComp, leaves, r);
    
    priority_queue<pair<int, int>, vector<pair<int, int>>> pq;
    for(auto i : leaves) {pq.emplace(make_pair(0, i)); vis[i] = true;}
    int rad = 0;
    
    while(!pq.empty()) {
        pair<int, int> top = pq.top(); pq.pop();
        rad = top.first;

        if(vis[top.second]) continue;

        for(auto i : adjList[top.second]) {
            if(!vis[i.first]) {
                pq.emplace(make_pair(i.second + top.first, i.first));
            }
        }

        vis[top.second] = true;
    }

    int d = 0;
    for(auto i : connComp) d = max(d, max(d1[i], d2[i]));

    return make_pair(d, rad);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    
    memset(vis, false, sizeof(vis));
    memset(d1, -1, sizeof(vis));
    memset(d2, -1, sizeof(vis));

    for(int i = 0; i < M; i++) {
        adjList[A[i]].push_back({B[i], T[i]});
        adjList[B[i]].push_back({A[i], T[i]});
    }

    vector<int> radii;
    vector<int> diams;
    int comps = 0;

    for(int i = 0; i < N; i++) {
        if(!vis[i]) {
            pair<int, int> ans = solve(i);
            diams.push_back(ans.first);
            radii.push_back(ans.second);
            comps++;
        }
    }

    sort(radii.begin(), radii.end());
    sort(diams.begin(), diams.end());

    if(comps == 1) {
        return diams[0];
    } else if (comps == 2) {
        return min(max(diams[0], diams[1]), radii[0] + radii[1] + L);
    }
    
}

int main() {
    fastIO;
    
    // how the hell to do this...
    
    return 0;
}

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

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:100:1: warning: control reaches end of non-void function [-Wreturn-type]
  100 | }
      | ^
/usr/bin/ld: /tmp/cc2NARYZ.o: in function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'; /tmp/ccORuSUa.o:dreaming.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status