QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#252494#6738. Coverucup-team191#WA 1103ms34732kbC++142.7kb2023-11-15 20:12:232023-11-15 20:12:24

Judging History

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

  • [2023-11-15 20:12:24]
  • 评测
  • 测评结果:WA
  • 用时:1103ms
  • 内存:34732kb
  • [2023-11-15 20:12:23]
  • 提交

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[MSK];

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

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: 1103ms
memory: 34732kb

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:

1366352489907

result:

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