제출 #486508

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
486508		aryan12	자매 도시 (APIO20_swap)	C++17	컴파일 에러	0 ms	0 KiB

swap

//#include "swap.h"

#include <cassert>
#include <cstdio>

#include <string>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////////////

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

const int MAXN = 1e5 + 5;
vector<array<int, 3> > edges(MAXN * 2);
int DP[20][MAXN * 3];

struct ufds {
    bool isLine;
    pair<int, int> endpoints;
    int parent, value, depth;

    ufds(int x) {
        isLine = true;
        endpoints = {x, x};
        parent = x;
        value = 1e9;
        depth = 0;
    } 
} *Node[MAXN * 3];

int Find(int x) {
    if(Node[x]->parent == x) {
        return x;
    }
    return Node[x]->parent = Find(Node[x]->parent);
}

void Unite(int a, int b, int new_idx, int cur_val) {
    int original_a = a, original_b = b;
    a = Find(a);
    b = Find(b);
    Node[a]->parent = new_idx;
    Node[b]->parent = new_idx;
    Node[new_idx]->value = cur_val;
    DP[0][a] = new_idx;
    DP[0][b] = new_idx;
    if(a == b || !Node[a]->isLine || !Node[b]->isLine) {
        Node[new_idx]->isLine = false;
        Node[new_idx]->endpoints = {-1, -1};
    }
    else {
        //cout << "a = " << a << ", b = " << b << "\n";
        //cout << "A Line = " << Node[a]->endpoints.first << ", " << Node[a]->endpoints.second << "\n";
        //cout << "B Line = " << Node[b]->endpoints.first << ", " << Node[b]->endpoints.second << "\n";
        if(Node[a]->endpoints.first != original_a) {
            swap(Node[a]->endpoints.first, Node[a]->endpoints.second);
        }
        if(Node[b]->endpoints.first != original_b) {
            swap(Node[b]->endpoints.first, Node[b]->endpoints.second);
        }
        if(original_a == Node[a]->endpoints.first && original_b == Node[b]->endpoints.first) {
            Node[new_idx]->isLine = true;
            Node[new_idx]->endpoints = {Node[a]->endpoints.second, Node[b]->endpoints.second};
        }
        else {
            Node[new_idx]->isLine = false;
            Node[new_idx]->endpoints = {-1, -1};
        }
    }
}

bool cmp(array<int, 3> a, array<int, 3> b) {
    return a[2] < b[2];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    for(int i = 0; i < 20; i++) {
        for(int j = 0; j < MAXN * 3; j++) {
            DP[i][j] = -1;
        }
    }
    for(int i = 0; i < M; i++) {
        edges[i] = {U[i], V[i], W[i]};
    }
    sort(edges.begin(), edges.begin() + M, cmp);
    int cur_new = N;
    for(int i = 0; i < MAXN * 3; i++) {
        Node[i] = new ufds(i);
    }
    for(int i = 0; i < M; i++) {
        //cout << Find(edges[i][0]) << " " << Find(edges[i][1]) << "\n"; 
        int x = Find(edges[i][0]), y = Find(edges[i][1]);
        //cout << "x = " << x << ", Node[x] is a line? " << Node[x]->isLine << "\n";
        if(x != y || Node[x]->isLine == true) {
            //cout << "Uniting edge: (" << edges[i][0] << ", " << edges[i][1] << ", " << edges[i][2] << ")\n";
            Unite(edges[i][0], edges[i][1], cur_new++, edges[i][2]);
        }
    }
    assert(cur_new <= MAXN * 3);
    for(int i = 1; i < 20; i++) {
        for(int j = 0; j < cur_new; j++) {
            if(DP[i - 1][j] != -1) {
                DP[i][j] = DP[i - 1][DP[i - 1][j]];
            }
            else {
                DP[i][j] = -1;
            }
        }
    }
}

bool Check(int val, int X, int Y) {
    for(int i = 19; i >= 0; i--) {
        if(DP[i][X] != -1 && Node[DP[i][X]]->value <= val) {
            X = DP[i][X];
        }
        if(DP[i][Y] != -1 && Node[DP[i][Y]]->value <= val) {
            Y = DP[i][Y];
        }
    }
    return (X == Y && Node[X]->isLine == false);
}

int getMinimumFuelCapacity(int X, int Y) {
    int ans = 1e9 + 2;
    int l = 0, r = 1e9;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(Check(mid, X, Y)) {
            r = mid - 1;
            ans = mid;
        }
        else {
            l = mid + 1;
        }
    }
    if(ans == 1e9 + 2) {
        ans = -1;
    }
    return ans;
}


/////////////////////////////////////////////////////////////////////////////////////////////////

int main() {
  int N, M;
  assert(2 == scanf("%d %d", &N, &M));
  
  std::vector<int> U(M), V(M), W(M);
  for (int i = 0; i < M; ++i) {
    assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
  }

  int Q;
  assert(1 == scanf("%d", &Q));

  std::vector<int> X(Q), Y(Q);
  for (int i = 0; i < Q; ++i) {
    assert(2 == scanf("%d %d", &X[i], &Y[i]));
  }

  init(N, M, U, V, W);
  
  std::vector<int> minimum_fuel_capacities(Q);
  for (int i = 0; i < Q; ++i) {
    minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
  }

  for (int i = 0; i < Q; ++i) {
    printf("%d\n", minimum_fuel_capacities[i]);
  }
  
  return 0;
}

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

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