QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#441712#8530. Cowntact Tracingarbuzick#17.391304 3ms38456kbC++203.7kb2024-06-14 17:18:522024-06-14 17:18:52

Judging History

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

  • [2024-06-14 17:18:52]
  • 评测
  • 测评结果：17.391304
  • 用时：3ms
  • 内存：38456kb
查看
  • [2024-06-14 17:18:52]
  • 提交

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][nights];
        }
    }
    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;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 4.34783
Accepted
time: 1ms
memory: 5596kb

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: 1ms
memory: 10012kb

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: 1ms
memory: 5600kb

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: 1ms
memory: 5608kb

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: 1ms
memory: 5704kb

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:

2
-1
-1
8
-1
2
-1
-1
-1
2
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: 3ms
memory: 38456kb

input:

400
11111111101111110011101111111111011111111111111111111111111111111111111111110111111111111111111101111111011111111101111111111111110111111111110110101111111111111111111111111011111111111111110111111111111011111111111111111111110111101111101110111111010011011111111111011111101111110110111111111111...

output:

-1
-1
9
-1
51
-1
12
18
23
363
14
30
-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: 38396kb

input:

400
11101111111111111111111110110111111111111111011111111111111011111111111111111010111111111110110111011111101111111111111101111111111010111111111111111111111111111111111111101111111111111110111111111111111111111111111111111111111111101011111111111111111110111101111111111111110111111111111111101111...

output:

2
-1
24
1
15
4
2
-1
101
47
-1
9
-1
3
2
3
374
-1
2
-1

result:

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

Test #11:

score: 0
Wrong Answer
time: 3ms
memory: 36532kb

input:

400
11010111101110111110111011010111101011011001111110101101000100011111110101011011011111011110111111111000011110101110011100111111101111101011101110111111111001100111111101101111011011101111111111011101110111111111111011111110111111000111111111111111111111010111101101111111111110111101101110011110...

output:

3
6
3
6
6
-1
-1
3
3
4
8
11
25
8
-1
50
16
-1
10
5

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

output:

result:
English 繁體中文 简体中文

Server Time: 2024-12-03 07:48:22 | OpenSource Project