QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#182846#6738. Coverucup-team004#WA 757ms36184kbC++203.1kb2023-09-18 16:54:282023-09-18 16:54:28

Judging History

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

  • [2023-09-18 16:54:28]
  • 评测
  • 测评结果:WA
  • 用时:757ms
  • 内存:36184kb
  • [2023-09-18 16:54:28]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 1E5;

int f[N];

int find(int x) {
    while (x != f[x]) {
        x = f[x] = f[f[x]];
    }
    return x;
}

i64 fen[N];
void add(int x, i64 y) {
    for (int i = x + 1; i <= N; i += i & -i) {
        fen[i - 1] += y;
    }
}

i64 sum(int x) {
    i64 res = 0;
    for (int i = x; i; i &= i - 1) {
        res += fen[i - 1];
    }
    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m, k;
    std::cin >> n >> m >> k;
    
    std::vector<std::vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    std::vector<std::vector<int>> q(n), ch(n);
    std::vector<int> a(m), b(m), w(m);
    for (int i = 0; i < m; i++) {
        std::cin >> a[i] >> b[i] >> w[i];
        a[i]--, b[i]--;
        q[a[i]].push_back(i);
        q[b[i]].push_back(i);
    }
    std::vector<int> vis(m, -1);
    std::vector<int> in(n), out(n);
    int cur = 0;
    std::vector<i64> dp(n), g(n);
    std::iota(f, f + n, 0);
    auto dfs = [&](auto self, int x, int p) -> void {
        if (p != -1) {
            adj[x].erase(std::find(adj[x].begin(), adj[x].end(), p));
        }
        in[x] = cur++;
        const int deg = adj[x].size();
        for (auto y : adj[x]) {
            self(self, y, x);
            f[y] = x;
        }
        for (auto i : q[x]) {
            if (vis[i] == -1) {
                vis[i] = x;
            } else {
                int lca = find(vis[i]);
                ch[lca].push_back(i);
            }
        }
        out[x] = cur;
        std::vector<i64> f(1 << deg);
        for (int i = 1; i < (1 << deg); i++) {
            int u = __builtin_ctz(i);
            f[i] = f[i & (i - 1)] + dp[adj[x][u]];
        }
        for (auto i : ch[x]) {
            int mask = 0;
            i64 val = w[i];
            if (a[i] != x) {
                int j = 0;
                while (out[adj[x][j]] <= in[a[i]]) {
                    j++;
                }
                mask |= 1 << j;
                val += dp[a[i]] + sum(in[a[i]] + 1);
            }
            if (b[i] != x) {
                int j = 0;
                while (out[adj[x][j]] <= in[b[i]]) {
                    j++;
                }
                mask |= 1 << j;
                val += dp[b[i]] + sum(in[b[i]] + 1);
            }
            int s = (1 << deg) - 1 - mask;
            for (int t = s; ; t = (t - 1) & s) {
                f[t | mask] = std::max(f[t | mask], f[t] + val);
                if (!t) {
                    break;
                }
            }
        }
        dp[x] = f.back();
        for (int i = 0; i < deg; i++) {
            int y = adj[x][i];
            dp[y] = f[(1 << deg) - 1 - (1 << i)];
            add(in[y], dp[y]);
            add(out[y], -dp[y]);
        }
    };
    dfs(dfs, 0, -1);
    
    std::cout << dp[0] << "\n";
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3512kb

input:

5 7 3
1 2
1 3
2 4
2 5
3 2 8
5 4 10
3 1 2
1 2 7
2 1 2
1 2 1
5 2 3

output:

19

result:

ok 1 number(s): "19"

Test #2:

score: -100
Wrong Answer
time: 757ms
memory: 36184kb

input:

100000 500000 12
2 1
3 2
4 2
5 2
6 5
7 2
8 5
9 3
10 2
11 2
12 5
13 1
14 1
15 1
16 1
17 1
18 1
19 1
20 1
21 1
22 1
23 1
24 12
25 2
26 2
27 2
28 2
29 2
30 15
31 30
32 23
33 26
34 22
35 30
36 26
37 3
38 3
39 3
40 3
41 3
42 3
43 3
44 3
45 3
46 3
47 20
48 21
49 4
50 4
51 4
52 4
53 4
54 4
55 4
56 4
57 4
5...

output:

3665948706670

result:

wrong answer 1st numbers differ - expected: '660925834533', found: '3665948706670'