QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#441709	#8530. Cowntact Tracing	arbuzick^#	13.043478	1ms	38704kb	C++20	3.7kb	2024-06-14 17:17:58	2024-06-14 17:17:58

Judging History

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

[2024-06-14 17:17:58]
评测

测评结果：13.043478
用时：1ms
内存：38704kb

查看

[2024-06-14 17:17:58]
提交

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];

int used[maxn];

int t = 0;

void dfs(int v, int nights, int prv = -1LL) {
    used[v] = t;
    dp2[v][0] = 0;
    for (auto u : g[v]) {
        if (used[u] < t) {
            dfs(u, nights, v);
            dp2[v][0] += dp1[u][0];
        }
    }
    for (int d = 1; d < nights; ++d) {
        dp2[v][d] = 0;
        for (auto u : g[v]) {
            if (u != prv) {
                dp2[v][d] += dp2[u][d - 1];
            }
        }
    }
    if (mn_dist[v] > nights) {
        dp1[v][0] = 1;
        for (auto u : g[v]) {
            if (u != prv) {
                if (nights == 0) {
                    dp1[v][0] += dp1[u][nights];
                } else {
                    dp1[v][0] += dp2[u][nights - 1];
                }
            }
        }
    }
    for (int d = 1; d <= nights; ++d) {
        int sum = 0;
        for (auto u : g[v]) {
            if (u != prv) {
                if (d == 0) {
                    sum += dp1[u][nights];
                } else {
                    sum += dp2[u][d - 1];
                }
            }
        }
        for (auto u : g[v]) {
            if (u != prv) {
                if (d == 0) {
                    sum -= dp1[u][nights];
                } else {
                    sum -= dp2[u][d - 1];
                }
                dp1[v][d] = min(dp1[v][d], sum + dp1[u][d - 1]);
                if (d == 0) {
                    sum += dp1[u][nights];
                } else {
                    sum += dp2[u][d - 1];
                }
            }
        }
    }
    for (int d = 1; d <= nights; ++d) {
        dp1[v][d] = min(dp1[v][d], dp1[v][d - 1]);
    }
    dp2[v][0] = min(dp2[v][0], dp1[v][nights]);
    for (int i = 1; i < nights; ++i) {
        dp2[v][i] = min(dp2[v][i], dp2[v][i - 1]);
    }
}

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') {
                for (int j = 0; j <= nights; ++j) {
                    dp1[i][j] = inf;
                    dp2[i][j] = inf;
                }
            }
        }
        t++;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '1' && used[i] < t) {
                dfs(i, nights);
                if (dp1[i][nights] >= inf) {
                    ans = -1;
                    break;
                }
                ans += dp1[i][nights];
            }
        }
        cout << ans << '\n';
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 4.34783

Accepted

time: 1ms

memory: 5600kb

input:

output:

result:

ok 6 lines

Test #2:

score: 4.34783

Accepted

time: 1ms

memory: 5712kb

input:

output:

result:

ok 11 lines

Test #3:

score: 4.34783

Accepted

time: 1ms

memory: 5648kb

input:

output:

3
1
1
-1
-1
-1

result:

ok 6 lines

Test #4:

score: 0

Wrong Answer

time: 1ms

memory: 5916kb

input:

output:

3
-1
-1
9
-1
-1
-1
-1
-1
4
-1

result:

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

Test #5:

score: 0

Wrong Answer

time: 0ms

memory: 5612kb

input:

output:

2
-1
-1
8
-1
2
-1
-1
-1
3
2

result:

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

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

input:

400
11111111101111110011101111111111011111111111111111111111111111111111111111110111111111111111111101111111011111111101111111111111110111111111110110101111111111111111111111111011111111111111110111111111111011111111111111111111110111101111101110111111010011011111111111011111101111110110111111111111...

output:

-1
-1
9
-1
56
-1
12
18
23
363
14
32
-1
-1
-1
-1
-1
-1
-1
-1

result:

wrong answer 3rd lines differ - expected: '11', found: '9'

Test #10:

score: 0

Wrong Answer

time: 0ms

memory: 36492kb

input:

400
11101111111111111111111110110111111111111111011111111111111011111111111111111010111111111110110111011111101111111111111101111111111010111111111111111111111111111111111111101111111111111110111111111111111111111111111111111111111111101011111111111111111110111101111111111111110111111111111111101111...

output:

result:

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

Test #11:

score: 0

Wrong Answer

time: 0ms

memory: 36648kb

input:

400
11010111101110111110111011010111101011011001111110101101000100011111110101011011011111011110111111111000011110101110011100111111101111101011101110111111111001100111111101101111011011101111111111011101110111111111111011111110111111000111111111111111111111010111101101111111111110111101101110011110...

output:

result:

wrong answer 2nd lines differ - expected: '7', found: '6'

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