제출 #563245

#제출 시각아이디문제언어결과실행 시간메모리
563245ngpin04도로 폐쇄 (APIO21_roads)C++14
컴파일 에러
0 ms0 KiB
#include <bits/stdc++.h> #include "roads.h" #define fi first #define se second #define mp make_pair #define TASK "" #define bit(x) (1LL << (x)) #define getbit(x, i) (((x) >> (i)) & 1) #define ALL(x) (x).begin(), (x).end() using namespace std; template <typename T1, typename T2> bool mini(T1 &a, T2 b) { if (a > b) {a = b; return true;} return false; } template <typename T1, typename T2> bool maxi(T1 &a, T2 b) { if (a < b) {a = b; return true;} return false; } mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r) { return l + rd() % (r - l + 1); } const int N = 1e5 + 5; const int oo = 1e9; const long long ooo = 1e18; const int mod = 1e9 + 7; // 998244353; const long double pi = acos(-1); vector <int> adj[N]; long long f[N][2]; long long dp[205][205]; int fr[N]; int to[N]; int w[N]; int n; vector <long long> sub1() { sort(w, w + (n - 1), greater <int>()); long long tot = accumulate(w, w + (n - 1), 0LL); vector <long long> res; res.push_back(tot); for (int i = 0; i < n - 1; i++) tot -= w[i], res.push_back(tot); return res; } vector <long long> sub2() { vector <long long> res; res.push_back(accumulate(w, w + (n - 1), 0LL)); for (int i = 0; i < n; i++) for (int j = 0; j < 2; j++) f[i][j] = ooo; f[0][0] = 0; for (int i = 1; i < n; i++) { f[i][0] = min(f[i - 1][0], f[i - 1][1]) + w[i - 1]; f[i][1] = f[i - 1][0]; } res.push_back(min(f[n - 1][0], f[n - 1][1])); for (int i = 2; i < n; i++) res.push_back(0); return res; } void dfs(int u, int k, int p = -1) { for (int i : adj[u]) { int v = fr[i] ^ to[i] ^ u; if (v == p) continue; dfs(v, k, u); } int deg = 0; for (int j = 1; j <= k; j++) dp[u][j] = ooo; vector <long long> f(k + 1, ooo), g(k + 1, ooo); f[0] = 0; for (int i : adj[u]) { int v = fr[i] ^ to[i] ^ u; if (v == p) continue; for (int cur = deg; cur >= 0; cur--) { if (cur + 1 <= k) mini(g[cur + 1], f[cur] + dp[v][k - 1]); mini(g[cur], f[cur] + dp[v][k] + w[i]); } deg++; mini(deg, k); for (int cur = 0; cur <= deg; cur++) { f[cur] = g[cur]; g[cur] = ooo; } } for (int j = 0; j <= k; j++) { dp[u][j] = f[j]; if (j > 0) mini(dp[u][j], dp[u][j - 1]); } } long long solve(int k) { dfs(1, k); return dp[1][k]; } vector <long long> sub3() { vector <long long> res; for (int i = 0; i < n - 1; i++) { adj[fr[i]].push_back(i); adj[to[i]].push_back(i); } for (int k = 0; k < n; k++) res.push_back(solve(k)); return res; } vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) { n = N; bool cond3 = (n <= 200); bool cond2 = true; for (int i = 0; i < n - 1; i++) { fr[i] = U[i]; to[i] = V[i]; w[i] = W[i]; cond2 &= fr[i] == i && to[i] == i + 1; } if (*max_element(ALL(U)) == 0) return sub1(); if (cond2) return sub2(); if (cond3) return sub3(); return vector<long long>(N, 0); } #include "grader.cpp"

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

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