QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#441707#8530. Cowntact TracingQwerty1232#4.347826 324ms21484kbC++234.6kb2024-06-14 17:16:322024-06-14 17:16:33

Judging History

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

  • [2024-06-14 17:16:33]
  • 评测
  • 测评结果：4.347826
  • 用时：324ms
  • 内存：21484kb
查看
  • [2024-06-14 17:16:32]
  • 提交

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 < dp[t].size(); i++) {
                            dp[v].rbegin()[i] = dp[v].rbegin()[i] + dp[t].rbegin()[i];
                            // dp[v].rbegin()[i] = std::min<int>(1e9, dp[v].rbegin()[i] + dp[t].rbegin()[i]);
                            dp2[v].rbegin()[i] = std::min<int>(dp2[v].rbegin()[i], dp2[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;
}
源文件, 语言: C++23

详细

Test #1:

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

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

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:

7
3
2
1
1
1
1
1
1
1
1

result:

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

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

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
12
-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: 324ms
memory: 20576kb

input:

100000
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

1
1
3
66
6
1
2
2
35
54
3
2
186
9
2
85
1
1
1
1

result:

wrong answer 4th lines differ - expected: '69', found: '66'

Test #7:

score: 0
Wrong Answer
time: 283ms
memory: 21484kb

input:

100000
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

2
2
69
3
2
218
8
3
97
3
3
3
2
3
10
4
3
3
2
2

result:

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

Test #8:

score: 0
Wrong Answer
time: 143ms
memory: 16600kb

input:

100000
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

4
2
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: '100000', found: '4'

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

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: 35ms
memory: 10084kb

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: 38ms
memory: 10008kb

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: 31ms
memory: 10180kb

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

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: 26ms
memory: 17564kb

input:

100000
11011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

5
-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: '5'

Test #23:

score: 0
Wrong Answer
time: 68ms
memory: 15500kb

input:

99901
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

-1
-1
-1
201
201
201
201
201
201
201
201
201
201
201
201
201
201
201
220
334

result:

wrong answer 2nd lines differ - expected: '200', found: '-1'
English 繁體中文 简体中文

服务器时间: 2024-12-12 03:16:20 | 开源项目