| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 338182 |
2020-12-22T15:58:20 Z |
minoum |
Džumbus (COCI19_dzumbus) |
C++17 |
|
86 ms |
41068 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MAXN = 1000+10;
const ll inf = 1e17;
int n, m;
ll dp[MAXN][MAXN][3], s[MAXN][MAXN], d[MAXN], sz[MAXN], d2[MAXN][3], mn[MAXN][MAXN];
vector <int> adj[MAXN], rs;
bool mark[MAXN];
void dfs(int v){
mark[v] = true; sz[v] = 1;
dp[v][0][0] = 0ll; dp[v][0][1] = d[v]; mn[v][0] = 0ll;
for(int u: adj[v]){
if(mark[u]) continue;
dfs(u);
for(int i = 0; i <= sz[u]+sz[v]; i++){
d2[i][0] = dp[v][i][0];
d2[i][1] = dp[v][i][1];
d2[i][2] = dp[v][i][2];
//d2[i][0] = d2[i][1] = d2[i][2] = inf;
}
for(int i = 0; i <= sz[v]; i++)
for(int j = i; j <= sz[u]+sz[v]; j++){
d2[j][0] = min(d2[j][0], dp[v][i][0]+mn[u][j-i]);
d2[j][1] = min(d2[j][1], dp[v][i][1]+dp[u][j-i][0]);
d2[j][2] = min(d2[j][2], dp[v][i][2]+min(dp[u][j-i][0], dp[u][j-i][2]));
if(j-i-1>=0) d2[j][2] = min(d2[j][2], dp[v][i][1]+dp[u][j-i-1][2]);
if(i-1>=0) d2[j][2] = min(d2[j][2], dp[v][i-1][1]+dp[u][j-i][2]);
if(j-i-1>=0) d2[j][2] = min(d2[j][2], dp[v][i][2]+dp[u][j-i-1][1]);
if(i-1>=0) d2[j][2] = min(d2[j][2], dp[v][i-1][2]+dp[u][j-i][1]);
if(j-i-2>=0) d2[j][2] = min(d2[j][2], dp[v][i][1]+dp[u][j-i-2][1]);
if(i-2>=0) d2[j][2] = min(d2[j][2], dp[v][i-2][1]+dp[u][j-i][1]);
if(i-1>=0 && j-i-1>=0) d2[j][2] = min(d2[j][2], dp[v][i-1][1]+dp[u][j-i-1][1]);
}
for(int i = 0; i <= sz[u]+sz[v]; i++){
dp[v][i][0] = min(inf, d2[i][0]);
dp[v][i][1] = min(inf, d2[i][1]);
dp[v][i][2] = min(inf, d2[i][2]);
}
sz[v] += sz[u];
}
for(int i = 0; i <= sz[v]; i++)
mn[v][i] = min(dp[v][i][0], min(dp[v][i][1], dp[v][i][2]));
return;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 0; i < n; i++){
cin >> d[i];
for(int j = 0; j <= n; j++) dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = s[i][j] = mn[i][j] = inf;
}
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v; u--; v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i = 0; i < n; i++)
if(!mark[i]){
dfs(i);
rs.push_back(i);
}
for(int i = 0; i <= n; i++)
for(int j = 1; j <= n; j++) s[i][j] = inf;
s[0][0] = 0ll;
int cnt = 0;
for(int i = 0; i < (int)rs.size(); i++){
int v = rs[i];
cnt += sz[v];
s[i+1][0] = 0ll;
for(int j = 1; j <= cnt; j++)
for(int k = 0; k <= min((int)sz[v], j); k++){
s[i+1][j] = min(s[i+1][j], mn[v][k]+s[i][j-k]);
}
}
vector <pair<ll, int>> ans;
cnt = (int)rs.size();
for(int i = 0; i <= n; i++)
if(s[1][i] != inf) ans.push_back({s[1][i], i});
sort(ans.begin(), ans.end());
for(int i = 1; i < (int)ans.size(); i++) ans[i].second = max(ans[i].second, ans[i-1].second);
int q;
cin >> q;
while(q--){
ll s1;
cin >> s1;
pair<ll, int> p = {s1, INT_MAX};
int ind = upper_bound(ans.begin(), ans.end(), p) - ans.begin() - 1;
cout << ans[ind].second << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
40044 KB |
Output is correct |
| 2 |
Correct |
33 ms |
40172 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
40044 KB |
Output is correct |
| 2 |
Correct |
33 ms |
40172 KB |
Output is correct |
| 3 |
Correct |
86 ms |
41068 KB |
Output is correct |
| 4 |
Correct |
83 ms |
41068 KB |
Output is correct |
| 5 |
Correct |
81 ms |
40556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
2796 KB |
Output is correct |
| 2 |
Incorrect |
42 ms |
2540 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
40044 KB |
Output is correct |
| 2 |
Correct |
33 ms |
40172 KB |
Output is correct |
| 3 |
Correct |
86 ms |
41068 KB |
Output is correct |
| 4 |
Correct |
83 ms |
41068 KB |
Output is correct |
| 5 |
Correct |
81 ms |
40556 KB |
Output is correct |
| 6 |
Correct |
45 ms |
2796 KB |
Output is correct |
| 7 |
Incorrect |
42 ms |
2540 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
