QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#252515 | #6738. Cover | ucup-team191# | AC ✓ | 1171ms | 37416kb | C++14 | 2.8kb | 2023-11-15 20:27:48 | 2023-11-15 20:27:49 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <vector>
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 1e5 + 500;
const int M = 5e5 + 500;
const int LOG = 17;
const int OFF = (1 << LOG);
const int MSK = (1 << 12);
vector < int > v[N], ch[N], sada[N];
int par[N][LOG], L[N], R[N], dep[N], tme;
int lc[M], a[M], b[M], ozn[N], w[M];
ll T[2 * OFF];
int n, m;
void dfs(int x, int lst){
dep[x] = dep[lst] + 1; par[x][0] = lst;
L[x] = tme++;
for(int y : v[x])
if(y != lst) dfs(y, x), ch[x].PB(y);
R[x] = tme - 1;
}
void prepare_lca(){
for(int j = 1;j < LOG;j++)
for(int i = 1;i <= n;i++)
par[i][j] = par[par[i][j - 1]][j - 1];
}
void update(int i, int a, int b, int lo, int hi, ll x) {
if(lo <= a && b <= hi) {
T[i] += x; return;
}
if(a > hi || b < lo) return;
update(2 * i, a, (a + b) / 2, lo, hi, x);
update(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, x);
}
ll query(int i) {
ll ret = 0;
for(i += OFF; i ; i /= 2)
ret += T[i];
return ret;
}
ll dp[MSK], slob[N];
void ubaci(int msk, int tko, ll sto) {
msk -= tko;
for(int st = msk; st ; st = (st - 1) & msk)
dp[st + tko] = max(dp[st + tko], dp[st] + sto);
dp[tko] = max(dp[tko], sto);
}
int digni(int x, int k) {
for(int i = 0;i < LOG;i++)
if(k & (1 << i)) x = par[x][i];
return x;
}
int lca(int x, int y) {
y = digni(y, dep[y] - dep[x]);
if(x == y) return x;
for(int i = LOG - 1;i >= 0;i--)
if(par[x][i] != par[y][i])
x = par[x][i], y = par[y][i];
return par[x][0];
}
void solve(int x) {
for(int y : ch[x]) solve(y);
for(int i = 0;i < (int)ch[x].size();i++)
ozn[ch[x][i]] = i;
int sz = (int)ch[x].size();
for(int i = 0;i < (1 << sz);i++) {
dp[i] = 0;
for(int j = 0;j < sz;j++)
if(i & (1 << j)) dp[i] += slob[ch[x][j]];
}
int ss = (1 << sz) - 1;
for(int t : sada[x]) {
if(a[t] == x) {
int pb = digni(b[t], dep[b[t]] - dep[x] - 1);
ubaci(ss, 1 << ozn[pb], query(L[b[t]]) + w[t]);
} else {
int pa = digni(a[t], dep[a[t]] - dep[x] - 1);
int pb = digni(b[t], dep[b[t]] - dep[x] - 1);
ubaci(ss, (1 << ozn[pb]) + (1 << ozn[pa]), query(L[a[t]]) + query(L[b[t]]) + w[t]);
}
}
slob[x] = dp[ss];
update(1, 0, OFF - 1, L[x], L[x], slob[x]);
for(int y : ch[x]) {
ll bez = dp[ss - (1 << ozn[y])];
update(1, 0, OFF - 1, L[y], R[y], bez);
}
}
int main(){ int kurac;
scanf("%d%d%d", &n, &m, &kurac);
for(int i = 1;i < n;i++) {
int x, y; scanf("%d%d", &x, &y);
v[x].PB(y), v[y].PB(x);
}
dfs(1, 1);
prepare_lca();
for(int i = 0;i < m;i++) {
scanf("%d%d%d", a + i, b + i, w + i);
if(dep[a[i]] > dep[b[i]]) swap(a[i], b[i]);
sada[lca(a[i], b[i])].PB(i);
}
solve(1);
printf("%lld\n", slob[1]);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 19444kb
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: 0
Accepted
time: 1107ms
memory: 35844kb
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:
660925834533
result:
ok 1 number(s): "660925834533"
Test #3:
score: 0
Accepted
time: 1138ms
memory: 34264kb
input:
100000 500000 12 2 1 3 2 4 1 5 4 6 2 7 5 8 2 9 7 10 8 11 3 12 11 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 22 24 8 25 2 26 2 27 2 28 2 29 2 30 2 31 2 32 2 33 26 34 27 35 23 36 13 37 3 38 3 39 3 40 3 41 3 42 3 43 3 44 3 45 3 46 3 47 14 48 8 49 4 50 4 51 4 52 4 53 4 54 4 55 4 56 4 57 4 58 4...
output:
664434138007
result:
ok 1 number(s): "664434138007"
Test #4:
score: 0
Accepted
time: 1132ms
memory: 34124kb
input:
100000 500000 12 2 1 3 1 4 2 5 3 6 4 7 2 8 7 9 2 10 6 11 4 12 8 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 13 24 23 25 2 26 2 27 2 28 2 29 2 30 2 31 2 32 2 33 26 34 31 35 33 36 33 37 3 38 3 39 3 40 3 41 3 42 3 43 3 44 3 45 3 46 3 47 34 48 16 49 4 50 4 51 4 52 4 53 4 54 4 55 4 56 4 57 4 58 ...
output:
639691495391
result:
ok 1 number(s): "639691495391"
Test #5:
score: 0
Accepted
time: 1143ms
memory: 33944kb
input:
100000 500000 12 2 1 3 1 4 2 5 1 6 5 7 4 8 2 9 1 10 4 11 8 12 7 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 14 22 14 23 21 24 20 25 2 26 2 27 2 28 2 29 2 30 2 31 2 32 2 33 2 34 23 35 31 36 7 37 3 38 3 39 3 40 3 41 3 42 3 43 3 44 3 45 3 46 3 47 3 48 29 49 4 50 4 51 4 52 4 53 4 54 4 55 4 56 4 57 4 58 3...
output:
662244733768
result:
ok 1 number(s): "662244733768"
Test #6:
score: 0
Accepted
time: 1171ms
memory: 34560kb
input:
100000 500000 12 2 1 3 1 4 1 5 1 6 3 7 1 8 4 9 3 10 7 11 2 12 5 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 14 21 12 22 11 23 9 24 20 25 2 26 2 27 2 28 2 29 2 30 2 31 2 32 2 33 2 34 2 35 14 36 30 37 3 38 3 39 3 40 3 41 3 42 3 43 3 44 3 45 3 46 24 47 38 48 35 49 4 50 4 51 4 52 4 53 4 54 4 55 4 56 4 57 4 58...
output:
669458090009
result:
ok 1 number(s): "669458090009"
Test #7:
score: 0
Accepted
time: 309ms
memory: 37276kb
input:
100000 500000 12 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 ...
output:
488921502446
result:
ok 1 number(s): "488921502446"
Test #8:
score: 0
Accepted
time: 289ms
memory: 36756kb
input:
100000 500000 12 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 16 41 40 42 41 43 42 44 33 45 44 46 45 47 46 48 47 49 48 50 49 51 50 ...
output:
468137226275
result:
ok 1 number(s): "468137226275"
Test #9:
score: 0
Accepted
time: 291ms
memory: 36308kb
input:
100000 500000 12 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 35 51 50 ...
output:
483733769728
result:
ok 1 number(s): "483733769728"
Test #10:
score: 0
Accepted
time: 318ms
memory: 36932kb
input:
100000 500000 12 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 ...
output:
478945297872
result:
ok 1 number(s): "478945297872"
Test #11:
score: 0
Accepted
time: 322ms
memory: 37416kb
input:
100000 500000 12 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 ...
output:
489443708266
result:
ok 1 number(s): "489443708266"
Test #12:
score: 0
Accepted
time: 538ms
memory: 25356kb
input:
10000 500000 12 2 1 3 2 4 1 5 1 6 2 7 5 8 2 9 8 10 6 11 8 12 4 13 11 14 1 15 6 16 5 17 10 18 17 19 12 20 8 21 16 22 1 23 5 24 21 25 23 26 3 27 18 28 6 29 8 30 15 31 1 32 30 33 17 34 23 35 5 36 24 37 33 38 25 39 34 40 1 41 24 42 11 43 6 44 18 45 28 46 25 47 32 48 40 49 29 50 43 51 33 52 9 53 2 54 20 ...
output:
560772428222
result:
ok 1 number(s): "560772428222"
Test #13:
score: 0
Accepted
time: 153ms
memory: 24880kb
input:
10000 500000 12 2 1 3 2 4 2 5 2 6 4 7 5 8 4 9 4 10 4 11 4 12 10 13 5 14 13 15 9 16 15 17 2 18 5 19 14 20 11 21 11 22 20 23 20 24 1 25 5 26 15 27 20 28 17 29 4 30 18 31 12 32 14 33 18 34 18 35 16 36 31 37 18 38 19 39 12 40 17 41 14 42 7 43 27 44 25 45 13 46 35 47 10 48 15 49 46 50 44 51 21 52 15 53 2...
output:
572767352204
result:
ok 1 number(s): "572767352204"
Test #14:
score: 0
Accepted
time: 281ms
memory: 25220kb
input:
10000 500000 12 2 1 3 1 4 2 5 2 6 2 7 4 8 7 9 7 10 2 11 9 12 3 13 1 14 7 15 9 16 8 17 2 18 13 19 12 20 2 21 16 22 8 23 13 24 8 25 20 26 25 27 14 28 4 29 28 30 4 31 12 32 13 33 24 34 1 35 21 36 5 37 16 38 28 39 35 40 28 41 13 42 20 43 19 44 16 45 40 46 28 47 3 48 5 49 14 50 2 51 4 52 47 53 47 54 15 5...
output:
585482767864
result:
ok 1 number(s): "585482767864"
Test #15:
score: 0
Accepted
time: 193ms
memory: 25008kb
input:
10000 500000 12 2 1 3 2 4 3 5 3 6 3 7 5 8 7 9 4 10 3 11 2 12 7 13 4 14 8 15 9 16 1 17 12 18 13 19 2 20 3 21 16 22 10 23 20 24 4 25 19 26 6 27 17 28 5 29 17 30 27 31 22 32 14 33 11 34 4 35 24 36 34 37 14 38 23 39 18 40 30 41 28 42 36 43 12 44 5 45 14 46 17 47 11 48 14 49 16 50 16 51 18 52 30 53 17 54...
output:
564574799774
result:
ok 1 number(s): "564574799774"
Test #16:
score: 0
Accepted
time: 211ms
memory: 24688kb
input:
10000 500000 12 2 1 3 1 4 2 5 2 6 4 7 6 8 5 9 8 10 7 11 7 12 5 13 1 14 5 15 11 16 9 17 3 18 4 19 10 20 8 21 2 22 11 23 18 24 10 25 8 26 16 27 22 28 11 29 20 30 12 31 4 32 19 33 27 34 6 35 1 36 24 37 18 38 30 39 32 40 10 41 9 42 15 43 34 44 27 45 34 46 7 47 34 48 39 49 32 50 13 51 11 52 38 53 17 54 5...
output:
575291114848
result:
ok 1 number(s): "575291114848"