QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #441748 | #8530. Cowntact Tracing | Qwerty1232# | 4.347826 | 349ms | 21552kb | C++23 | 4.7kb | 2024-06-14 17:44:06 | 2024-06-14 17:44:07 |
Judging History
answer
#include <bits/stdc++.h>
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::string s;
std::cin >> s;
std::vector<std::vector<int>> gr(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
std::cin >> u >> v;
u--;
v--;
gr[u].push_back(v);
gr[v].push_back(u);
}
std::vector<bool> used(n);
std::vector<int> roots;
for (int i = 0; i < n; i++) {
if (used[i]) {
continue;
}
auto dfs = [&](auto dfs, int v, int f) {
if (s[v] == '0') {
return;
}
used[v] = true;
for (int t : gr[v]) {
if (t != f) {
dfs(dfs, t, v);
}
}
};
roots.push_back(i);
dfs(dfs, i, -1);
}
std::vector<int> diam(n, -1);
for (int u : roots) {
std::pair<int, int> max(0, u);
int cnt = 0;
for (int i = 0; i < 2; i++) {
cnt = 0;
auto dfs = [&](auto dfs, int v, int d, int f) {
if (s[v] == '0') {
return;
}
if (std::find_if(gr[v].begin(), gr[v].end(), [&](int t) { return s[t] == '0'; }) != gr[v].end()) {
cnt++;
max = std::max(max, {d, v});
}
for (int t : gr[v]) {
if (t != f) {
dfs(dfs, t, d + 1, v);
}
}
};
int u = max.second;
max = {0, u};
dfs(dfs, u, 0, -1);
}
if (cnt == 0) {
continue;
}
diam[u] = max.first;
}
std::vector<int> sz(n);
for (int u : roots) {
auto dfs = [&](auto dfs, int v, int f) {
if (s[v] == '0') {
return;
}
sz[v] = 1;
;
for (int& t : gr[v]) {
if (t != f && s[t] == '1') {
dfs(dfs, t, v);
sz[v] += sz[t];
} else {
t = -1;
}
}
std::erase(gr[v], -1);
std::sort(gr[v].begin(), gr[v].end(), [&](int a, int b) { return sz[a] > sz[b]; });
};
dfs(dfs, u, -1);
}
int q;
std::cin >> q;
for (int test = 0; test < q; test++) {
int d;
std::cin >> d;
for (int u : roots) {
if (diam[u] != -1 && 2 * d > diam[u]) {
d = -1;
break;
}
}
if (d == -1) {
std::cout << "-1\n";
continue;
}
std::vector<std::vector<int>> dp(n), dp2(n);
int ans_total = 0;
for (int root : roots) {
auto dfs = [&](auto dfs, int v) -> void {
if (gr[v].empty()) {
dp[v] = {0};
dp2[v] = {1};
return;
}
for (int t : gr[v]) {
dfs(dfs, t);
}
dp[v] = std::move(dp[gr[v][0]]);
dp2[v] = std::move(dp2[gr[v][0]]);
dp[v].push_back(dp2[v].rbegin()[std::min<int>(dp2[v].size() - 1, d)]);
dp2[v].push_back(dp[v].rbegin()[std::min<int>(dp[v].size() - 1, d)] + 1);
for (int i = 1; i < gr[v].size(); i++) {
int t = gr[v][i];
dp[t].push_back(dp2[t].rbegin()[std::min<int>(dp2[t].size() - 1, d)]);
dp2[t].push_back(dp[t].rbegin()[std::min<int>(dp[t].size() - 1, d)] + 1);
if (dp[v].size() < dp[t].size()) {
dp[v].swap(dp[t]);
dp2[v].swap(dp2[t]);
}
for (int i = 0; i <= std::min<int>(d, dp[t].size()); i++) {
dp[v].rbegin()[i] = dp[v].rbegin()[i] + dp[t].rbegin()[i];
dp2[v].rbegin()[i] = std::min<int>({
dp2[v].rbegin()[i] + dp2[t].rbegin()[i],
dp2[v].rbegin()[i] + dp[t].rbegin()[std::min<int>(dp[t].size() - 1, d - i)],
dp[v].rbegin()[std::min<int>(dp[v].size() - 1, d - i)] + dp[t].rbegin()[i],
});
}
}
};
dfs(dfs, root);
int ans = dp2[root].rbegin()[std::min<int>(dp[root].size() - 1, d)];
ans_total += ans;
}
std::cout << ans_total << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 4.34783
Accepted
time: 0ms
memory: 3836kb
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: 0
Wrong Answer
time: 0ms
memory: 3624kb
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 1 1 1 1 1 1 1 1 1
result:
wrong answer 3rd lines differ - expected: '2', found: '1'
Test #3:
score: 0
Memory Limit Exceeded
input:
5 11100 1 2 2 3 3 4 4 5 6 0 1 2 3 4 5
output:
result:
Test #4:
score: 0
Wrong Answer
time: 0ms
memory: 3488kb
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:
-1 -1 -1 14 -1 -1 -1 -1 -1 -1 -1
result:
wrong answer 1st lines differ - expected: '2', found: '-1'
Test #5:
score: 0
Memory Limit Exceeded
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:
result:
Test #6:
score: 0
Wrong Answer
time: 349ms
memory: 20460kb
input:
100000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
0 0 3 52 5 0 1 2 26 40 1 6 148 10 0 67 1 0 1 1
result:
wrong answer 1st lines differ - expected: '1', found: '0'
Test #7:
score: 0
Wrong Answer
time: 251ms
memory: 21552kb
input:
100000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
4 2 72 2 4 201 14 8 89 3 3 3 1 4 14 5 5 4 2 1
result:
wrong answer 1st lines differ - expected: '3', found: '4'
Test #8:
score: 0
Wrong Answer
time: 147ms
memory: 16444kb
input:
100000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
100000 33334 33333 33333 33333 33333 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
wrong answer 4th lines differ - expected: '1', found: '33333'
Test #9:
score: 0
Time Limit Exceeded
input:
400 11111111101111110011101111111111011111111111111111111111111111111111111111110111111111111111111101111111011111111101111111111111110111111111110110101111111111111111111111111011111111111111110111111111111011111111111111111111110111101111101110111111010011011111111111011111101111110110111111111111...
output:
result:
Test #10:
score: 0
Memory Limit Exceeded
input:
400 11101111111111111111111110110111111111111111011111111111111011111111111111111010111111111110110111011111101111111111111101111111111010111111111111111111111111111111111111101111111111111110111111111111111111111111111111111111111111101011111111111111111110111101111111111111110111111111111111101111...
output:
result:
Test #11:
score: 0
Memory Limit Exceeded
input:
400 11010111101110111110111011010111101011011001111110101101000100011111110101011011011111011110111111111000011110101110011100111111101111101011101110111111111001100111111101101111011011101111111111011101110111111111111011111110111111000111111111111111111111010111101101111111111110111101101110011110...
output:
result:
Test #12:
score: 0
Memory Limit Exceeded
input:
6000 1110011111111111110111111111111111111011011111011110111111110111101011111111110111111110110111111111111111111111111111111111111111101111011111111111111111111011111111111111111111111111111111111111111111111110111111111111111111111111011111111111011111101101111111111111111111111111111111110111111...
output:
result:
Test #13:
score: 0
Memory Limit Exceeded
input:
6000 1111111110011111111101111111111101111111111110011111111011111111111111111110110110011011111110111110111111101111111011110111111111101111111111111001111101110111110111111111111111111111111111111010111111111111111101111111110111111111111111111011111111111111111111111111101111111111010111110111111...
output:
result:
Test #14:
score: 0
Wrong Answer
time: 2ms
memory: 3976kb
input:
6000 1101111110111110101111111111111111111110100111111111111111110111101111111111111111111111111111111111111001111111111111111111111111111111111011111111011110111111110111111111110011111111111111111111111111111111110111111111101111111111100111111111110111110111111011011111110101111111111101111001111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
wrong answer 1st lines differ - expected: '29', found: '-1'
Test #15:
score: 0
Wrong Answer
time: 24ms
memory: 9916kb
input:
100000 11111111101111111101111011100111111011111101000111011001111010011010111110101001110111111110111111110011111111111111110110111110111111110100111011111111111011111101111111001111101101111011010110110011010111111011111111111011111011110110110111111011111001100100011011111111100011010110111011110...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
wrong answer 1st lines differ - expected: '189', found: '-1'
Test #16:
score: 0
Memory Limit Exceeded
input:
100000 11111100010011111111001101110011001111000111010011101100101100011101111101010011111111000101111111111111011110011110110111101111101101111011110111001110111111101101111111111101011110101111111111011110111110111111111111011101111111110110111011110011111111101110111011110111111111110001111011111...
output:
result:
Test #17:
score: 0
Wrong Answer
time: 40ms
memory: 9912kb
input:
100000 11111111111111111111111111111110101111111011111111111011111111111101111111101111111111111101111111111111111111111111111111101101111111111111111111101111101001111111111110111111110111111110111110111111111111111111111011111101111011101011111111111111111111111111110111111101111111110111101111110...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
wrong answer 2nd lines differ - expected: '120', found: '-1'
Test #18:
score: 0
Memory Limit Exceeded
input:
100000 11111111111111011111111111011101111111111111111111111111111101111001111111111010111110111111111110111111111011111111111011111111111111111111111111011111111111111111111111011111111111110011111110111111111110111111111101111111111111111111111111111101111111110111111101111101111111111111101111111...
output:
result:
Test #19:
score: 0
Wrong Answer
time: 34ms
memory: 10220kb
input:
100000 11111111111111111111111111110111111111111001111111111111111111110111110111111111111111101111111111111111011110111111111111110011111111111110010111101100111111111111011111111111111111111011111110011111111101010111111111011111111110111111001111011111111111111111111111111111111111111111111111111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
wrong answer 1st lines differ - expected: '50', found: '-1'
Test #20:
score: 0
Memory Limit Exceeded
input:
100000 11111111111111111110101111111111111011110101111111111011111111110111111111111111011111111111100111111101111111111111101101011111111111111111111111111111111111111111111111111011111110111111111111111111011111111111111111111111111111111111111111111101111111101111111111111111111011101111111111111...
output:
result:
Test #21:
score: 0
Wrong Answer
time: 31ms
memory: 9860kb
input:
100000 00110111111011100111110111000111101111101001010100110101111001111111100011100110001111101100110110010011001011101011110111101011111111111110111101101111111111101110011111001111111111111101111111010111011010101111011110011111101101101010111011011111010110110010111100011010111101110010111110111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
wrong answer 1st lines differ - expected: '136', found: '-1'
Test #22:
score: 0
Wrong Answer
time: 23ms
memory: 17424kb
input:
100000 11011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
100001 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
wrong answer 1st lines differ - expected: '99999', found: '100001'
Test #23:
score: 0
Wrong Answer
time: 80ms
memory: 15500kb
input:
99901 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
-1 -1 -1 203 205 207 209 211 213 215 217 219 221 223 225 227 229 231 5136 33567
result:
wrong answer 2nd lines differ - expected: '200', found: '-1'