QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#441647#8530. Cowntact Tracingarbuzick#13.043478 3ms10548kbC++205.4kb2024-06-14 16:56:322024-06-14 16:56:33

Judging History

你现在查看的是最新测评结果

  • [2024-06-14 16:56:33]
  • 评测
  • 测评结果:13.043478
  • 用时:3ms
  • 内存:10548kb
  • [2024-06-14 16:56:32]
  • 提交

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;
        bool fl = false;
        for (int i = 1; i < (int)kids.size(); ++i) {
            if (d == 0) {
                sum += dp_ans[kids[i]];
                fl = true;
            } else {
                if (dp2[kids[i]].size() < d) {
                    break;
                }
                sum += dp2[kids[i]][d - 1];
                fl = true;
            }
        }
        dp1[v][pos] += sum;
        if (!fl) {
            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]][(int)dp1[kids[i]].size() - 1 - (nights - (d + 1))]);
            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;
}

詳細信息

Test #1:

score: 4.34783
Accepted
time: 0ms
memory: 10412kb

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: 3ms
memory: 10312kb

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
0
0
0
0
1
1
1
1

result:

wrong answer 3rd lines differ - expected: '2', found: '1'

Test #3:

score: 4.34783
Accepted
time: 3ms
memory: 10548kb

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: 10312kb

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: 0
Wrong Answer
time: 0ms
memory: 10352kb

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:

0
-1
-1
8
0
0
-1
-1
-1
3
1

result:

wrong answer 1st lines differ - expected: '-1', found: '0'

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: 0ms
memory: 10500kb

input:

400
11111111101111110011101111111111011111111111111111111111111111111111111111110111111111111111111101111111011111111101111111111111110111111111110110101111111111111111111111111011111111111111110111111111111011111111111111111111110111101111101110111111010011011111111111011111101111110110111111111111...

output:

0
0
0
0
4
0
0
0
2
363
0
4
0
0
-1
4
-1
0
0
-1

result:

wrong answer 1st lines differ - expected: '-1', found: '0'

Test #10:

score: 0
Wrong Answer
time: 0ms
memory: 10536kb

input:

400
11101111111111111111111110110111111111111111011111111111111011111111111111111010111111111110110111011111101111111111111101111111111010111111111111111111111111111111111111101111111111111110111111111111111111111111111111111111111111101011111111111111111110111101111111111111110111111111111111101111...

output:

0
-1
0
0
0
0
0
0
36
1
0
0
-1
0
0
0
374
-1
0
-1

result:

wrong answer 1st lines differ - expected: '-1', found: '0'

Test #11:

score: 0
Wrong Answer
time: 0ms
memory: 10524kb

input:

400
11010111101110111110111011010111101011011001111110101101000100011111110101011011011111011110111111111000011110101110011100111111101111101011101110111111111001100111111101101111011011101111111111011101110111111111111011111110111111000111111111111111111111010111101101111111111110111101101110011110...

output:

1
1
0
1
1
-1
-1
0
0
1
1
1
2
1
-1
6
1
-1
1
1

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...

output:


result: