QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#252512 | #6738. Cover | ucup-team191# | WA | 1132ms | 32864kb | C++14 | 2.8kb | 2023-11-15 20:24:39 | 2023-11-15 20:24:40 |
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[pb]) + 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[pa]) + query(L[pb]) + 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 10136kb
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: 1132ms
memory: 32864kb
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:
682118367870
result:
wrong answer 1st numbers differ - expected: '660925834533', found: '682118367870'