QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #441612 | #8530. Cowntact Tracing | arbuzick# | 21.73913 | 5ms | 10796kb | C++20 | 5.3kb | 2024-06-14 16:40:11 | 2024-06-14 16:40:16 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int maxn = 5005, inf = 1e9 + 7;
vector<int> g[maxn];
int mn_dist[maxn];
// int dp1[maxn][maxn], dp2[maxn][maxn];
deque<int> dp1[maxn], dp2[maxn];
int dp_ans[maxn];
int used[maxn];
int t = 0;
void dfs(int v, int nights, int prv = -1LL) {
used[v] = t;
vector<int> kids;
for (auto u : g[v]) {
if (used[u] < t) {
dfs(u, nights, v);
kids.push_back(u);
}
}
sort(kids.begin(), kids.end(), [&](int a, int b) {
return dp1[a].size() > dp1[b].size();
});
if (kids.empty()) {
dp1[v] = {inf};
if (mn_dist[v] > nights) {
dp1[v] = {1};
}
dp2[v] = {0};
dp_ans[v] = dp1[v][0];
return;
}
swap(dp1[v], dp1[kids[0]]);
if (dp1[v].size() == nights + 1) {
dp1[v].pop_front();
}
dp1[v].push_back(inf);
if (mn_dist[v] > nights) {
dp1[v].back() = 1;
for (int i = 0; i < (int)kids.size(); ++i) {
if (nights == 0) {
dp1[v].back() += dp_ans[kids[i]];
} else {
if (dp2[kids[i]].size() >= nights) {
dp1[v].back() += dp2[kids[i]][nights - 1];
}
}
}
}
int pos = 0;
for (int d = nights + 1 - (int)dp1[v].size(); d < nights; ++d) {
int sum = 0;
for (int i = 1; i < (int)kids.size(); ++i) {
if (d == 0) {
sum += dp_ans[kids[i]];
} else {
if (dp2[kids[i]].size() < d) {
break;
}
sum += dp2[kids[i]][d - 1];
}
}
dp1[v][pos] += sum;
if (sum == 0) {
break;
}
if (d == 0) {
sum += dp_ans[kids[0]];
} else {
if (dp2[kids[0]].size() >= d) {
sum == dp2[kids[0]][d - 1];
}
}
for (int i = 1; i < (int)kids.size(); ++i) {
if (d == 0) {
sum -= dp_ans[kids[i]];
} else {
if (dp2[kids[i]].size() < d) {
break;
}
sum -= dp2[kids[i]][d - 1];
}
dp1[v][pos] = min(dp1[v][pos], sum + dp1[kids[i]][d + 1 - (nights + 1 - (int)dp1[kids[i]].size())]);
if (d == 0) {
sum += dp_ans[kids[i]];
} else {
if (dp2[kids[i]].size() < d) {
break;
}
sum += dp2[kids[i]][d - 1];
}
}
pos++;
}
// pos--;
// if (pos > 0) {
// dp1[v][pos] = min(dp1[v][pos], dp1[v][pos + 1]);
// dp1[v][pos] = min(dp1[v][pos], dp1[v].back());
// for (int i = pos - 1; i >= 0; --i) {
// dp1[v][i] = min(dp1[v][i], dp1[v][i + 1]);
// }
// } else {
// dp1[v][0] = min(dp1[v][0], dp1[v].back());
// }
for (int i = (int)dp1[v].size() - 2; i >= 0; --i) {
dp1[v][i] = min(dp1[v][i], dp1[v][i + 1]);
}
swap(dp2[v], dp2[kids[0]]);
if (dp2[v].size() == nights + 1) {
dp2[v].pop_back();
}
dp2[v].push_front(0);
for (int i = 0; i < (int)kids.size(); ++i) {
dp2[v][0] += dp_ans[kids[i]];
for (int d = 0; d < (int)dp2[kids[i]].size() && d + 1 < (int)dp2[v].size(); ++i) {
dp2[v][d + 1] += dp2[kids[i]][d];
}
}
dp2[v][0] = min(dp2[v][0], dp1[v][0]);
for (int i = 1; i < (int)dp2[v].size(); ++i) {
dp2[v][i] = min(dp2[v][i], dp2[v][i - 1]);
}
dp_ans[v] = dp1[v][0];
}
void solve() {
int n;
cin >> n;
string s;
cin >> s;
for (int i = 0; i < n; ++i) {
mn_dist[i] = inf;
}
for (int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;
a--, b--;
if (s[a] == '1' && s[b] == '1') {
g[a].push_back(b);
g[b].push_back(a);
} else {
mn_dist[a] = 1;
mn_dist[b] = 1;
}
}
queue<int> q;
for (int i = 0; i < n; ++i) {
if (s[i] == '1' && mn_dist[i] == 1) {
q.push(i);
}
}
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto u : g[v]) {
if (mn_dist[u] > mn_dist[v] + 1) {
mn_dist[u] = mn_dist[v] + 1;
q.push(u);
}
}
}
int qs;
cin >> qs;
while (qs--) {
int nights;
cin >> nights;
for (int i = 0; i < n; ++i) {
if (s[i] == '1') {
dp1[i].clear();
dp2[i].clear();
}
}
t++;
int ans = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '1' && used[i] < t) {
dfs(i, nights);
if (dp_ans[i] >= inf) {
ans = -1;
break;
}
ans += dp_ans[i];
}
}
cout << ans << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 4.34783
Accepted
time: 0ms
memory: 10248kb
input:
5 11111 1 2 2 3 3 4 4 5 6 5 4 3 2 1 0
output:
1 1 1 1 2 5
result:
ok 6 lines
Test #2:
score: 4.34783
Accepted
time: 0ms
memory: 10540kb
input:
10 1111111111 1 2 2 3 2 4 2 5 2 6 6 7 7 8 8 9 9 10 11 0 1 2 3 4 5 6 7 8 9 10
output:
10 3 2 1 1 1 1 1 1 1 1
result:
ok 11 lines
Test #3:
score: 4.34783
Accepted
time: 4ms
memory: 10568kb
input:
5 11100 1 2 2 3 3 4 4 5 6 0 1 2 3 4 5
output:
3 1 1 -1 -1 -1
result:
ok 6 lines
Test #4:
score: 4.34783
Accepted
time: 3ms
memory: 10288kb
input:
10 1101111111 6 4 6 7 4 3 4 2 7 9 9 5 5 1 2 8 2 10 11 2 9 5 0 3 6 10 8 7 1 4
output:
2 -1 -1 9 -1 -1 -1 -1 -1 3 -1
result:
ok 11 lines
Test #5:
score: 4.34783
Accepted
time: 0ms
memory: 10364kb
input:
10 1101011111 7 8 8 2 2 10 10 9 9 4 8 1 10 6 6 3 3 5 11 4 8 6 0 5 3 7 9 10 1 2
output:
-1 -1 -1 8 -1 2 -1 -1 -1 3 2
result:
ok 11 lines
Test #6:
score: 0
Runtime Error
input:
100000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
result:
Test #7:
score: 0
Runtime Error
input:
100000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
result:
Test #8:
score: 0
Runtime Error
input:
100000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
result:
Test #9:
score: 0
Wrong Answer
time: 5ms
memory: 10760kb
input:
400 11111111101111110011101111111111011111111111111111111111111111111111111111110111111111111111111101111111011111111101111111111111110111111111110110101111111111111111111111111011111111111111110111111111111011111111111111111111110111101111101110111111010011011111111111011111101111110110111111111111...
output:
0 0 -1 0 4 0 -1 -1 3 363 -1 4 0 0 -1 4 -1 0 1 -1
result:
wrong answer 1st lines differ - expected: '-1', found: '0'
Test #10:
score: 0
Wrong Answer
time: 0ms
memory: 10796kb
input:
400 11101111111111111111111110110111111111111111011111111111111011111111111111111010111111111110110111011111101111111111111101111111111010111111111111111111111111111111111111101111111111111110111111111111111111111111111111111111111111101011111111111111111110111101111111111111110111111111111111101111...
output:
0 -1 2 0 2 1 0 -1 36 3 0 2 -1 1 1 1 374 -1 0 -1
result:
wrong answer 1st lines differ - expected: '-1', found: '0'
Test #11:
score: 0
Wrong Answer
time: 0ms
memory: 10464kb
input:
400 11010111101110111110111011010111101011011001111110101101000100011111110101011011011111011110111111111000011110101110011100111111101111101011101110111111111001100111111101101111011011101111111111011101110111111111111011111110111111000111111111111111111111010111101101111111111110111101101110011110...
output:
1 2 0 2 2 -1 -1 0 1 1 2 2 3 2 -1 8 3 -1 2 2
result:
wrong answer 1st lines differ - expected: '3', found: '1'
Test #12:
score: 0
Runtime Error
input:
6000 1110011111111111110111111111111111111011011111011110111111110111101011111111110111111110110111111111111111111111111111111111111111101111011111111111111111111011111111111111111111111111111111111111111111111110111111111111111111111111011111111111011111101101111111111111111111111111111111110111111...
output:
result:
Test #13:
score: 0
Runtime Error
input:
6000 1111111110011111111101111111111101111111111110011111111011111111111111111110110110011011111110111110111111101111111011110111111111101111111111111001111101110111110111111111111111111111111111111010111111111111111101111111110111111111111111111011111111111111111111111111101111111111010111110111111...
output:
result:
Test #14:
score: 0
Runtime Error
input:
6000 1101111110111110101111111111111111111110100111111111111111110111101111111111111111111111111111111111111001111111111111111111111111111111111011111111011110111111110111111111110011111111111111111111111111111111110111111111101111111111100111111111110111110111111011011111110101111111111101111001111...
output:
result:
Test #15:
score: 0
Runtime Error
input:
100000 11111111101111111101111011100111111011111101000111011001111010011010111110101001110111111110111111110011111111111111110110111110111111110100111011111111111011111101111111001111101101111011010110110011010111111011111111111011111011110110110111111011111001100100011011111111100011010110111011110...
output:
result:
Test #16:
score: 0
Runtime Error
input:
100000 11111100010011111111001101110011001111000111010011101100101100011101111101010011111111000101111111111111011110011110110111101111101101111011110111001110111111101101111111111101011110101111111111011110111110111111111111011101111111110110111011110011111111101110111011110111111111110001111011111...
output:
result:
Test #17:
score: 0
Runtime Error
input:
100000 11111111111111111111111111111110101111111011111111111011111111111101111111101111111111111101111111111111111111111111111111101101111111111111111111101111101001111111111110111111110111111110111110111111111111111111111011111101111011101011111111111111111111111111110111111101111111110111101111110...
output:
result:
Test #18:
score: 0
Runtime Error
input:
100000 11111111111111011111111111011101111111111111111111111111111101111001111111111010111110111111111110111111111011111111111011111111111111111111111111011111111111111111111111011111111111110011111110111111111110111111111101111111111111111111111111111101111111110111111101111101111111111111101111111...
output:
result:
Test #19:
score: 0
Runtime Error
input:
100000 11111111111111111111111111110111111111111001111111111111111111110111110111111111111111101111111111111111011110111111111111110011111111111110010111101100111111111111011111111111111111111011111110011111111101010111111111011111111110111111001111011111111111111111111111111111111111111111111111111...
output:
result:
Test #20:
score: 0
Runtime Error
input:
100000 11111111111111111110101111111111111011110101111111111011111111110111111111111111011111111111100111111101111111111111101101011111111111111111111111111111111111111111111111111011111110111111111111111111011111111111111111111111111111111111111111111101111111101111111111111111111011101111111111111...
output:
result:
Test #21:
score: 0
Runtime Error
input:
100000 00110111111011100111110111000111101111101001010100110101111001111111100011100110001111101100110110010011001011101011110111101011111111111110111101101111111111101110011111001111111111111101111111010111011010101111011110011111101101101010111011011111010110110010111100011010111101110010111110111...
output:
result:
Test #22:
score: 0
Runtime Error
input:
100000 11011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
result:
Test #23:
score: 0
Runtime Error
input:
99901 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...