제출 #700501

#제출 시각아이디문제언어결과실행 시간메모리
700501Forested철로 (IOI14_rail)C++17
56 / 100
485 ms98696 KiB
#include "rail.h" #include <bits/stdc++.h> using namespace std; using i32 = int; using i64 = long long; template <typename T> using Vec = vector<T>; #define OVERRIDE4(a, b, c, d, ...) d #define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i) #define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i) #define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__) #define ALL(x) begin(x), end(x) #define PER(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i) template <typename T> bool chmin(T &x, const T &y) { if (x > y) { x = y; return true; } else { return false; } } template <typename T> bool chmax(T &x, const T &y) { if (x < y) { x = y; return true; } else { return false; } } constexpr i32 INF = 1001001001; constexpr i64 INF64 = 3003003003003003003; void findLocation(int n, int first, int location[], int stype[]) { Vec<Vec<i32>> dist(n, Vec<i32>(n, 0)); REP(i, n) REP(j, i) { dist[i][j] = dist[j][i] = getDistance(i, j); } Vec<i32> mn(n, INF), mnrg(n, 0); REP(i, n) { REP(j, n) { if (i != j && chmin(mn[i], dist[i][j])) { mnrg[i] = j; } } } i32 y = mnrg[0]; i32 x = mnrg[y]; stype[x] = 1; location[x] = first + mn[0] - mn[y]; stype[y] = 2; location[y] = first + mn[0]; REP(i, n) { if (i == x || i == y) { continue; } if (dist[i][x] < dist[i][y]) { continue; } if (mnrg[i] != y && dist[i][mnrg[i]] + dist[mnrg[i]][y] == dist[i][y]) { continue; } stype[i] = 1; location[i] = location[y] - dist[i][y]; } REP(i, n) { if (i == x || i == y) { continue; } if (dist[i][x] < dist[i][y]) { continue; } if (mnrg[i] != y && dist[i][mnrg[i]] + dist[mnrg[i]][y] == dist[i][y]) { stype[i] = 2; location[i] = location[mnrg[i]] + mn[i]; } } REP(i, n) { if (i == x || i == y) { continue; } if (dist[i][x] > dist[i][y]) { continue; } if (mnrg[i] != x && dist[i][mnrg[i]] + dist[mnrg[i]][x] == dist[i][x]) { continue; } stype[i] = 2; location[i] = location[x] + dist[i][x]; } REP(i, n) { if (i == x || i == y) { continue; } if (dist[i][x] > dist[i][y]) { continue; } if (mnrg[i] != x && dist[i][mnrg[i]] + dist[mnrg[i]][x] == dist[i][x]) { stype[i] = 1; location[i] = location[mnrg[i]] - mn[i]; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...