QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#456884#7103. Red Black Treeucup-team3282WA 1425ms119908kbC++143.1kb2024-06-28 16:21:542024-06-28 16:21:57

Judging History

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

  • [2024-06-28 16:21:57]
  • 评测
  • 测评结果:WA
  • 用时:1425ms
  • 内存:119908kb
  • [2024-06-28 16:21:54]
  • 提交

answer

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
const int N = 2e5+9;
int fa[N][21], dep[N], dis[N], n, m, q, r[N], isred[N], anc[N], nr = 1, node[N], k, tot, dfn[N], LG[N], st[N][21], rev[N][21], pos[N], cnt, T;
vector<pair<int, int>> adj[N];
void dfs1(int u, int f, int d) {
	fa[u][0] = f; dfn[++tot] = u; dep[tot] = d; pos[u] = tot;
	if (!isred[u]) anc[u] = nr;
	int tmp = nr;
	for (auto i : adj[u]) {
		if (i.fi == f) continue;
		if (isred[i.fi]) nr = i.fi;
		dis[i.fi] = dis[u] + i.se;
		dfs1(i.fi, u, d + 1);
        dfn[++tot] = u; dep[tot] = d;
	}
	
	nr = tmp;
}

void init() {
    for (int i = 2; i <= tot; i++) LG[i] = LG[i >> 1] + 1;
    for (int i = 1; i <= tot; i++) {
        st[i][0] = dep[i];
        rev[i][0] = dfn[i];
    }

    for (int j = 1; j <= LG[tot]; j++) {
        for (int i = 1; i + (1 << j) - 1 <= tot; i++) {
            if (st[i][j - 1] < st[i + (1 << (j - 1))][j - 1]) st[i][j] = st[i][j - 1], rev[i][j] = rev[i][j - 1];
            else st[i][j] = st[i + (1 << (j - 1))][j - 1], rev[i][j] = rev[i + (1 << (j - 1))][j - 1];
        }
    }
}

int query(int l, int r) {
	int k = LG[r - l + 1];
    return st[l][k] < st[r - (1 << k) + 1][k] ? rev[l][k] : rev[r - (1 << k) + 1][k];
}

int lca(int x, int y) {
    if (pos[x] > pos[y]) swap(x, y);
    return query(pos[x], pos[y]);
}

bool check(int lim) {
	int cc = 0;
	for (int i = 1; i <= k; i++) {
		int u = node[i];
		if (dis[u] - dis[anc[u]] <= lim) continue;
		cc++;
	}
	
	if (cc == 0) return true;
	int zx = 0;
	for (int i = 1; i <= k; i++) {
		int u = node[i];
		if (dis[u] - dis[anc[u]] > lim) {
			if (!zx) {
                zx = u;
                continue;
            }

			zx = lca(zx, u);
		}
	}
	
	int mx = -1;
	for (int i = 1; i <= k; i++) {
		int u = node[i];
		if (dis[u] - dis[anc[u]] > lim) {
			mx = max(mx, dis[u]);
		}
	}
	
	return mx - dis[zx] <= lim;
}

void solve() {
	cin >> n >> m >> q;
	memset(dis, 0, sizeof(int) * (2 * n + 9));
	memset(isred, 0, sizeof(int) * (2 * n + 9));
	memset(dep, 0, sizeof(int) * (2 * n + 9));
	memset(anc, 0, sizeof(int) * (2 * n + 9));
    memset(pos, 0, sizeof(int) * (2 * n + 9));
    memset(dfn, 0, sizeof(int) * (2 * n + 9));
	nr = 1;
	for (int i = 0; i <= n; i++) adj[i].clear();
	for (int i = 1; i <= m; i++) {
		cin >> r[i];
		isred[r[i]] = true;
		anc[r[i]] = r[i];
	}
	
	for (int i = 1, u, v, w; i < n; i++) {
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}

    tot = 0;
	
	dfs1(1, 0, 1);
    init();
	
	while (q--) {
        cnt++;
		cin >> k;
		for (int i = 1; i <= k; i++) {
			cin >> node[i];
		}
		
		int l = 0, r = 1e9, ans = 0;
		while (l <= r) {
			int mid = (l + r) >> 1;
            if (cnt == 18) cout << mid << endl;
			if (check(mid)) {
				ans = mid;
				r = mid - 1;
			} else l = mid + 1;
		}
		
		if (cnt == 18 || T != 522) cout << ans << "\n";
	}
}

signed main() {
	//freopen("B.in", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> T;
	for (int i = 1; i <= T; i++) {
		solve();
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
12 2 4
1 9
1 2 1
2 3 4
3 4 3
3 5 2
2 6 2
6 7 1
6 8 2
2 9 5
9 10 2
9 11 3
1 12 10
3 3 7 8
4 4 5 7 8
4 7 8 10 11
3 4 5 12
3 2 3
1 2
1 2 1
1 3 1
1 1
2 1 2
3 1 2 3

output:

4
5
3
8
0
0
0

result:

ok 7 lines

Test #2:

score: -100
Wrong Answer
time: 1425ms
memory: 119908kb

input:

522
26 1 3
1
1 4 276455
18 6 49344056
18 25 58172365
19 9 12014251
2 1 15079181
17 1 50011746
8 9 2413085
23 24 23767115
22 2 26151339
26 21 50183935
17 14 16892041
9 26 53389093
1 20 62299200
24 18 56114328
11 2 50160143
6 26 14430542
16 7 32574577
3 16 59227555
3 15 8795685
4 12 5801074
5 20 57457...

output:

500000000
750000000
625000000
687500000
718750000
703125000
695312500
691406250
693359375
692382812
691894531
691650390
691528320
691467285
691436767
691421508
691413879
691417693
691419600
691420554
691421031
691421269
691421388
691421448
691421478
691421463
691421470
691421474
691421476
691421475
...

result:

wrong answer 1st lines differ - expected: '148616264', found: '500000000'