#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 1e3 + 5;
const int oo = 1e9 + 1;
vector <int> adj[N];
int dp[N][N][2][2];
int f[N][2][2];
int g[N][2][2];
int val[N];
int sz[N];
int a[N];
int n,m;
bool vis[N];
void mini(int &a, int b) {
if (a > b)
a = b;
if (a > oo)
a = oo;
}
void dfs(int u, int p) {
vis[u] = true;
for (int v : adj[u])
if (!vis[v])
dfs(v, u);
for (int i = 0; i <= n; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
f[i][j][k] = g[i][j][k] = oo;
f[0][0][0] = 0;
f[0][1][0] = a[u];
sz[u] = 1;
for (int v : adj[u]) if (v != p) {
for (int l = 0; l <= sz[u]; l++)
for (int i = 0; i < 2; i++)
for (int k = 0; k < 2; k++)
for (int r = 0; r <= sz[v]; r++)
for (int j = 0; j < 2; j++)
for (int t = 0; t < 2; t++) {
int node = l + r + (i & j) * (!k + !t);
int used = k | (i & j);
mini(g[node][i][used], f[l][i][k] + dp[v][r][j][t]);
}
sz[u] += sz[v];
for (int l = 0; l <= sz[u]; l++)
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++) {
f[l][i][j] = g[l][i][j];
g[l][i][j] = oo;
}
}
for (int i = 0; i <= sz[u]; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
dp[u][i][j][k] = f[i][j][k];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= m; i++) {
int u,v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
a[0] = oo;
for (int i = 1; i <= n; i++) if (!vis[i]){
dfs(i, -1);
adj[0].push_back(i);
}
dfs(0, -1);
for (int i = n; i >= 0; i--) {
val[i] = oo;
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
val[i] = min(val[i], dp[0][i][j][k]);
if (i < m)
val[i] = min(val[i], val[i + 1]);
}
int q; cin >> q;
while (q--) {
int x; cin >> x;
int res = upper_bound(val, val + n + 1, x) - (val + 1);
cout << res << "\n";
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
42 ms |
8780 KB |
Output is correct |
2 |
Correct |
51 ms |
9468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
42 ms |
8780 KB |
Output is correct |
2 |
Correct |
51 ms |
9468 KB |
Output is correct |
3 |
Correct |
86 ms |
12176 KB |
Output is correct |
4 |
Correct |
108 ms |
11512 KB |
Output is correct |
5 |
Correct |
112 ms |
10812 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
41 ms |
2760 KB |
Output is correct |
2 |
Correct |
46 ms |
2512 KB |
Output is correct |
3 |
Correct |
47 ms |
3020 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
42 ms |
8780 KB |
Output is correct |
2 |
Correct |
51 ms |
9468 KB |
Output is correct |
3 |
Correct |
86 ms |
12176 KB |
Output is correct |
4 |
Correct |
108 ms |
11512 KB |
Output is correct |
5 |
Correct |
112 ms |
10812 KB |
Output is correct |
6 |
Correct |
41 ms |
2760 KB |
Output is correct |
7 |
Correct |
46 ms |
2512 KB |
Output is correct |
8 |
Correct |
47 ms |
3020 KB |
Output is correct |
9 |
Correct |
71 ms |
6704 KB |
Output is correct |
10 |
Correct |
84 ms |
7240 KB |
Output is correct |
11 |
Correct |
105 ms |
6852 KB |
Output is correct |