| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 499872 |
2021-12-29T21:14:21 Z |
Eyed |
Džumbus (COCI19_dzumbus) |
C++14 |
|
277 ms |
20460 KB |
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll INF = 1e14;
const ll MOD = 1e9 + 7;
//Problem: https://oj.uz/problem/view/COCI19_dzumbus
ll n, m, q;
ll arr[1001];
vector<ll> forest[1001];
vector<ll> dpArr[1001][3];
bool vis[1001];
void dfs2(ll x) {
vis[x] = true;
for (ll node : forest[x]) if (!vis[node]) dfs2(node);
}
void dfs(ll x, ll p) {
dpArr[x][0].resize(1);
dpArr[x][1].resize(1);
dpArr[x][2].resize(1);
dpArr[x][0][0] = 0; //disregarded
dpArr[x][1][0] = arr[x]; //not connected yet, but exist at top
dpArr[x][2][0] = INF; //already connected
for (ll node : forest[x]) {
if (node == p) continue;
dfs(node, x);
ll t = node;
ll s = dpArr[node][0].size() + dpArr[x][0].size() + 1;
vector<ll> nArr0(s, INF);
vector<ll> nArr1(s, INF);
vector<ll> nArr2(s, INF);
for (ll i = 0; i < dpArr[x][0].size(); ++i) {
for (ll j = 0; j < dpArr[node][0].size(); ++j) {
nArr0[i + j] = min(nArr0[i+j], dpArr[x][0][i] + min(dpArr[t][0][j], min(dpArr[t][1][j], dpArr[t][2][j])));
nArr1[i + j] = min(nArr1[i + j], dpArr[x][1][i] + dpArr[t][0][j]);
nArr2[i + j] = min(nArr2[i + j], dpArr[x][2][i] + min(dpArr[t][2][j], dpArr[t][0][j]));
nArr2[i + j + 1] = min(nArr2[i + j + 1], dpArr[x][2][i] + dpArr[t][1][j]);
nArr2[i + j + 2] = min(nArr2[i + j + 2], dpArr[x][1][i] + dpArr[t][1][j]);
nArr2[i + j + 1] = min(nArr2[i + j + 1], dpArr[x][1][i] + dpArr[t][2][j]);
}
}
//for (ll j = 0; j < s; ++j) nArr1[j] = min(nArr1[j], nArr0[j]);
dpArr[x][0] = nArr0;
dpArr[x][1] = nArr1;
dpArr[x][2] = nArr2;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (ll i = 1; i <= n; ++i) cin >> arr[i];
arr[0] = 1e9 + 1;
for (ll i = 0; i < m; ++i) {
ll a, b;
cin >> a >> b;
forest[a].push_back(b);
forest[b].push_back(a);
}
for (ll i = 1; i <= n; ++i) {
if (!vis[i]) {
dfs2(i);
forest[0].push_back(i);
forest[i].push_back(0);
}
}
dfs(0, 0);
//for (ll i = 0; i < dpArr[0][0].size(); ++i) {
// dpArr[0][0][i] = min(dpArr[0][0][i], min(dpArr[0][1][i], dpArr[0][2][i]));
// if (i == 2) dpArr[0][0][1] = dpArr[0][0][2];
// //cout << dpArr[0][0][i] << " ";
//}
dpArr[0][0][1] = dpArr[0][0][2];
//cout << endl;
cin >> q;
for (ll i = 0; i < q; ++i) {
ll s;
cin >> s;
ll l = 0;
ll r = dpArr[0][0].size() - 1;
while (l < r) {
ll mid = (l + r + 1) / 2;
if (dpArr[0][0][mid] <= s) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
return 0;
}
Compilation message
dzumbus.cpp: In function 'void dfs(ll, ll)':
dzumbus.cpp:44:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for (ll i = 0; i < dpArr[x][0].size(); ++i) {
| ~~^~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:45:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (ll j = 0; j < dpArr[node][0].size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
14540 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
20460 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
14540 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
20460 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
277 ms |
1388 KB |
Output is correct |
| 2 |
Incorrect |
250 ms |
1044 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
14540 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
20460 KB |
Output isn't correct |
