제출 #1055199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1055199		Kipras	Swapping Cities (APIO20_swap)	C++17	컴파일 에러	0 ms	0 KiB

swap

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
//#include "swap.h"

constexpr ll maxN = 1e5+10;
constexpr ll inf = 1e18;

ll par[5*maxN], timeP[5*maxN], cycle[5*maxN], sz[5*maxN];
ll n, m;
vector<ll> adj[maxN*5];
vector<pair<ll, pair<ll, ll>>> edges;
ll curInd = maxN + 5;

ll find(ll node, ll t) {
    if(par[node]==node)return node;
    if(timeP[node]<=t) {
        return find(par[node], t);
    }
    return node;
}

void unite(ll a, ll b, ll t, bool is){
    a = find(a, t);
    b = find(b, t);
    if(a==b){
        cycle[a]=min(cycle[a], t);
        cycle[b]=min(cycle[b], t);
        return;
    }
    if(sz[a]>sz[b]) {
        swap(a, b);
    }

    if(cycle[a]==0||cycle[b]==0) {
        if(is) {
            if(cycle[a]==0)cycle[a]=t;
            if(cycle[b]==0)cycle[b]=t;
        }

        sz[b]+=sz[a];
        par[a]=b;
        timeP[a]=t;

        if(cycle[a]==0&&cycle[b]!=0)
            cycle[a]=cycle[b];
        else if(cycle[b]==0&&cycle[a]!=0)
            cycle[b]=cycle[a];
        return;
    }
    par[a]=curInd;
    par[b]=curInd;
    par[curInd]=curInd;
    sz[curInd]=sz[a]+sz[b];
    timeP[a]=t;
    timeP[b]=t;
    cycle[curInd]=t;
    curInd++;

}

void init(int N, int M, vector<int> V, vector<int> U, vector<int> W) {
    n=N; m=M;
    for(int i = 0; i < m; i++) {
        edges.push_back({W[i], {U[i], V[i]}});
    }
    for(int i = 0; i <= n; i++) {
        par[i]=i;
        sz[i]=1;
        cycle[i]=inf;
        timeP[i]=inf;
    }
    sort(edges.begin(), edges.end());
    for(auto edge : edges) {
        ll vvv = edge.second.first, uuu = edge.second.second;
        ll www = edge.first;
        adj[vvv].push_back(uuu);
        adj[uuu].push_back(vvv);
        bool is = false;
        if(adj[vvv].size()>2||adj[uuu].size()>2)is=true;
        unite(vvv, uuu, www, is);
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    ll l = 0, h = 1e15;
    while(l < h && l < static_cast<ll>(1e10)) {
        ll m = (l+h)/2;
        ll v1 = find(X, m), v2 = find(Y, m);
        //cout<<m<<" "<<X<<" "<<Y<<" "<<l<<" "<<h<<" "<<v1<<" "<<v2<<" "<<cycle[v1]<<" "<<cycle[v2]<<"\n";
        if(v1==v2&&cycle[v1]<=m) {
            h=m;
        }else l = m+1;
    }
    if(h>static_cast<ll>(1e10)) {
        return -1;
    }else return static_cast<int>(l);
}

int main() {

    ios_base::sync_with_stdio(false);cin.tie(nullptr);

    int N, M;
    vector<int> V, U, W;
    cin>>N>>M;
    for(int i = 0; i < M; i++) {
        int aa;
        cin>>aa;
        V.push_back(aa);
    }
    for(int i = 0; i < M; i++) {
        int aa;
        cin>>aa;
        U.push_back(aa);
    }
    for(int i = 0; i < M; i++) {
        int aa;
        cin>>aa;
        W.push_back(aa);
    }
    init(N, M, V, U, W);
    ll Q;
    cin>>Q;
    for(int i = 0; i < Q; i++) {
        int aa, bb;
        cin>>aa>>bb;
        cout<<getMinimumFuelCapacity(aa, bb)<<"\n";
    }

}

/*

5 6
0 0 1 1 1 2
1 2 2 3 4 3
4 4 1 2 10 3
3
1 2
2 4
0 1


3 2
0 0
1 2
5 5
1
1 2


*/

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

/usr/bin/ld: /tmp/ccEmOKAy.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccvdcEuy.o:swap.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status