| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 736142 | 2023-05-05T09:04:19 Z | marvinthang | Džumbus (COCI19_dzumbus) | C++17 | 54 ms | 25548 KB |
/******************************
* author : @marvinthang *
* date : 09 / 02 / 2022 *
******************************/
#include <bits/stdc++.h>
using namespace std;
#define superspeed ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
#define file(name) if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
template <class U, class V> ostream & operator << (ostream& out, const pair<U, V> &p) { return out << '(' << p.first << ", " << p.second << ')'; }
template <class T> ostream & operator << (ostream &out, const vector<T> &vt) { out << '{'; for (size_t i = 0; i + 1 < vt.size(); i++) out << vt[i] << ", "; if (!vt.empty()) out << vt.back(); return out << '}'; }
const int MOD = 1e9 + 7;
const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int dir[] = {0, 1, 0, -1, 0}; // {0, 1, 1, -1, -1, 1, 0, -1, 0};
const long long oo = 1e15;
const int MAX = 1003;
int N, M, Q, treeSize[MAX];
long long D[MAX], F[MAX][MAX][2], G[MAX][MAX][2];
int res[200005];
pair <int, int> queries[200005];
vector <int> adj[MAX];
inline void minimize(long long &a, long long b) { if (a > b) a = b; }
void calc(int u, int par = 0) {
if (u) for (int &v: adj[u]) if (v != par) calc(v, u);
treeSize[u] = 1;
for (int i = 1; i <= (int) adj[u].size(); ++i) {
int v = adj[u][i - 1];
if (v == par) {
for (int j = 0; j <= treeSize[u]; ++j) {
G[i][j][0] = G[i - 1][j][0];
G[i][j][1] = G[i - 1][j][1];
}
continue;
}
for (int j = 0; j <= treeSize[u] + treeSize[v]; ++j) G[i][j][0] = G[i][j][1] = oo;
for (int a = 0; a <= treeSize[u]; ++a) {
for (int b = 0; b <= treeSize[v]; ++b) {
minimize(G[i][a + b][0], G[i - 1][a][0] + min(F[v][b][0], F[v][b][1]));
if (a) {
minimize(G[i][a + b][1], G[i - 1][a - 1][0] + D[u] + F[v][b][1]);
if (b) minimize(G[i][a + b][1], G[i - 1][a - 1][0] + D[u] + F[v][b - 1][0] + D[v]);
}
minimize(G[i][a + b][1], G[i - 1][a][1] + min(F[v][b][0], F[v][b][1]));
if (b) minimize(G[i][a + b][1], G[i - 1][a][1] + F[v][b - 1][0] + D[v]);
}
}
treeSize[u] += treeSize[v];
}
for (int i = 0; i <= treeSize[u]; ++i) {
F[u][i][0] = G[(int) adj[u].size()][i][0];
F[u][i][1] = G[(int) adj[u].size()][i][1];
}
}
int main(void) {
superspeed;
file("coci1920_r1_dzumbus");
scanf("%d%d", &N, &M);
D[0] = oo;
for (int i = 1; i <= N; ++i) scanf("%lld", D + i);
while (M--) {
int u, v; scanf("%d%d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
memset(F, -1, sizeof(F));
for (int i = 0; i <= N; ++i) G[0][i][0] = G[0][i][1] = oo;
G[0][0][0] = 0;
for (int i = 1; i <= N; ++i) {
if (F[i][0][0] == -1) {
calc(i);
adj[0].push_back(i);
}
}
calc(0);
for (int i = N; i >= 0; --i) minimize(F[0][i][0], F[0][i + 1][0]);
scanf("%d", &Q);
for (int i = 1; i <= Q; ++i) {
scanf("%d", &queries[i].first);
queries[i].second = i;
}
sort(queries + 1, queries + 1 + Q);
int cur = 0;
for (int i = 1; i <= Q; ++i) {
while (cur < N && F[0][cur + 1][0] <= queries[i].first) ++cur;
res[queries[i].second] = cur;
}
for (int i = 1; i <= Q; ++i) printf("%d\n", res[i]);
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 11 ms | 16340 KB | Output is correct |
| 2 | Correct | 10 ms | 16340 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 11 ms | 16340 KB | Output is correct |
| 2 | Correct | 10 ms | 16340 KB | Output is correct |
| 3 | Correct | 47 ms | 20752 KB | Output is correct |
| 4 | Correct | 54 ms | 21368 KB | Output is correct |
| 5 | Correct | 49 ms | 20968 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 46 ms | 20460 KB | Output is correct |
| 2 | Correct | 45 ms | 20388 KB | Output is correct |
| 3 | Correct | 42 ms | 20960 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 11 ms | 16340 KB | Output is correct |
| 2 | Correct | 10 ms | 16340 KB | Output is correct |
| 3 | Correct | 47 ms | 20752 KB | Output is correct |
| 4 | Correct | 54 ms | 21368 KB | Output is correct |
| 5 | Correct | 49 ms | 20968 KB | Output is correct |
| 6 | Correct | 46 ms | 20460 KB | Output is correct |
| 7 | Correct | 45 ms | 20388 KB | Output is correct |
| 8 | Correct | 42 ms | 20960 KB | Output is correct |
| 9 | Correct | 45 ms | 20896 KB | Output is correct |
| 10 | Correct | 51 ms | 23488 KB | Output is correct |
| 11 | Correct | 52 ms | 25548 KB | Output is correct |