QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#182846 | #6738. Cover | ucup-team004# | WA | 757ms | 36184kb | C++20 | 3.1kb | 2023-09-18 16:54:28 | 2023-09-18 16:54:28 |
Judging History
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'