제출 #486508

#제출 시각아이디문제언어결과실행 시간메모리
486508aryan12자매 도시 (APIO20_swap)C++17
컴파일 에러
0 ms0 KiB
//#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