제출 #1339358

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1339358		aaaaaaaa	가장 긴 여행 (IOI23_longesttrip)	C++20	컴파일 에러	0 ms	0 KiB

longesttrip

#include <bits/stdc++.h>
#include "longesttrip.h"

using namespace std;

const int mxN = 261;

#define all(x) x.begin(), x.end()
vector<int> adj[mxN];
deque<int> path[2][mxN];

set<pair<int, int>> current_edges;

bool are_connected(vector<int> a, vector<int> b){
    int u = a[0], v = b[0];
    if(current_edges.find({u, v}) != current_edges.end()) return 1;
    if(current_edges.find({v, u}) != current_edges.end()) return 1;
    return 0;
}


vector<int> longest_trip(int N, int D)
{

    vector<int> in(N + 5, 0), ans;

    for(int i = 0; i < N; ++i) adj[i].clear(), path[0][i].clear(), path[1][i].clear(), in[i] = 0;

    for(int i = 0; i < N; ++i){
        for(int j = i + 1; j < N; ++j){
            bool edge = are_connected({i}, {j});
            if(edge){
                adj[j].push_back(i);
                in[i] += 1;
            }
        }
    }

    queue<int> que;

    for(int i = 0; i < N; ++i){
        if(in[i] == 0) que.push(i);
        path[0][i] = path[1][i] = {i};
    }

    while((int) que.size()){
        auto tp = que.front();
        que.pop();
        for(auto v : adj[tp]){
            if((int) path[0][v].size() < (int) path[0][tp].size() + 1){
                swap(path[0][v], path[1][v]);
                path[0][v] = path[0][tp];
                path[0][v].push_front(v);
            } else if((int) path[1][v].size() < (int) path[0][tp].size() + 1){
                path[1][v] = path[0][tp];
                path[1][v].push_front(v);
            } else if((int) path[1][v].size() < (int) path[1][tp].size() + 1){
                path[1][v] = path[1][tp];
                path[1][v].push_front(v);
            }
            if(--in[v] == 0) que.push(v);
        }
    }

    int len = 0;

    for(int i = 0; i < N; ++i) {
        len = max(len, (int) path[0][i].size() + (int) path[1][i].size() - 1);
    }

    for(int i = 0; i < N; ++i){
        if(len == ((int) path[0][i].size() + (int) path[1][i].size() - 1)) {
            for(int j = (int) path[1][i].size() - 1; j >= 1; --j) ans.push_back(path[1][i][j]);
            for(auto it : path[0][i]) ans.push_back(it);
            break;
        }
    }

    return ans;
}




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

    int n, m;
    cin >> n >> m;

    for(int i = 0, u, v; i < m; ++i){
        cin >> u >> v;
        current_edges.insert({u, v});
    }

    vector<int> ans = longest_trip(n, 0);

    for(auto v : ans) cout << v << "\n";

    return 0;
}

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

/usr/bin/ld: /tmp/ccbGXdfZ.o: in function `are_connected(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)':
stub.cpp:(.text+0x0): multiple definition of `are_connected(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'; /tmp/ccZ9V2MT.o:longesttrip.cpp:(.text+0x200): first defined here
/usr/bin/ld: /tmp/ccbGXdfZ.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccZ9V2MT.o:longesttrip.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status