QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#160802#7103. Red Black Treeucup-team266#AC ✓779ms28808kbC++143.2kb2023-09-02 21:27:202023-09-02 21:27:20

Judging History

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

  • [2023-09-02 21:27:20]
  • 评测
  • 测评结果:AC
  • 用时:779ms
  • 内存:28808kb
  • [2023-09-02 21:27:20]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
const int Mod = 1e9 + 7;
const int inv2 = (Mod+1) / 2;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
inline int sign(int a){ return (a&1) ? (Mod-1) : 1; }
inline void uadd(int &a, int b){ a += b-Mod; a += (a>>31) & Mod; }
inline void usub(int &a, int b){ a -= b, a += (a>>31) & Mod; }
inline void umul(int &a, int b){ a = (int)(1ll * a * b % Mod); }
inline int add(int a, int b){ a += b-Mod; a += (a>>31) & Mod; return a; }
inline int sub(int a, int b){ a -= b, a += (a>>31) & Mod; return a; }
inline int mul(int a, int b){ a = (int)(1ll * a * b % Mod); return a; }
int qpow(int b, int p){ int ret = 1; while(p){ if(p&1) umul(ret, b); umul(b, b), p >>= 1; } return ret; }
int fact[200200], invfact[200200], pw2[200200], invpw2[200200];
void initfact(int n){
	pw2[0] = 1; for(int i = 1; i <= n; ++i) pw2[i] = mul(pw2[i-1], 2);
	invpw2[0] = 1; for(int i = 1; i <= n; ++i) invpw2[i] = mul(invpw2[i-1], (Mod+1) / 2);
	fact[0] = 1; for(int i = 1; i <= n; ++i) fact[i] = mul(fact[i-1], i);
	invfact[n] = qpow(fact[n], Mod-2); for(int i = n; i > 0; --i) invfact[i-1] = mul(invfact[i], i);
}
inline void chmax(int &a, int b){ (b>a) ? (a=b) : 0; }

int n, m, q;
vector<pii> g[100100];
int par[100100], dept[100100], lind[100100], rind[100100], ord[100100], cdfn = 0;
ll dist[100100], C[100100];

void dfs0(int u, int fa){
	lind[u] = cdfn, ord[cdfn] = u, ++cdfn;
	rep(i, (int)g[u].size()){
		int t = g[u][i].first, w = g[u][i].second;
		if(t == fa) continue;
		dept[t] = dept[u] + 1, dist[t] = dist[u] + w, par[t] = u, C[t] = min(C[t], C[u] + w);
		dfs0(t, u);
	}
	rind[u] = cdfn;
}
int st[22][100100], qlog[100100];
int lca(int u, int v){
	if(u == v) return u;
	u = lind[u], v = lind[v];
	if(u > v) swap(u, v);
	++u;
	int l = qlog[v - u];
	u = st[l][u], v = st[l][v - (1<<l) + 1];
	return par[(dept[u] < dept[v]) ? u : v];
}

void solve(){
	cin >> n >> m >> q;
	rep(i, n) g[i].clear();
	fill(C, C + n, inf);
	cdfn = 0;
	rep(i, m){
		int r; cin >> r; --r;
		C[r] = 0;
	}
	rep(i, n-1){
		int u, v, w;
		cin >> u >> v >> w;
		--u, --v;
		g[u].emplace_back(v, w);
		g[v].emplace_back(u, w);
	}

	dfs0(0, -1);
	rep(i, n) st[0][i] = ord[i];
	rep(i, 20) rep(j, n){
		st[i+1][j] = st[i][j];
		if(j + (1<<i) < n && dept[st[i][j + (1<<i)]] < dept[st[i][j]]) st[i+1][j] = st[i][j + (1<<i)];
	}

	while(q--){
		int K;
		cin >> K;
		vi p(K);
		rep(i, K) cin >> p[i], --p[i];
		sort(p.begin(), p.end(), [&](int lh, int rh){ return C[lh] < C[rh]; });
		ll ans = C[p[K-1]], curdep = 0;
		int l = p[K-1];
		for(int i = K-1; i >= 0; --i){
			ll cur = (i ? C[p[i-1]] : 0);
			l = lca(l, p[i]);
			//cout << i << ": " << cur << " " << l << " " << curdep << " " << dist[l] << endl;
			curdep = max(curdep, dist[p[i]]);
			ans = min(ans, max(cur, curdep - dist[l]));
		}
		cout << ans << "\n";
	}
}

int main(){
	//freopen("b.in", "r", stdin);
	//freopen("b.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);

	for(int i = 2; i <= 100000; ++i) qlog[i] = qlog[i>>1] + 1;

	int T;
	cin >> T;
	while(T--)
		solve();

	return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 18604kb

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: 0
Accepted
time: 779ms
memory: 28808kb

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:

148616264
148616264
0
319801028
319801028
255904892
317070839
1265145897
1265145897
1072765445
667742619
455103436
285643094
285643094
285643094
317919339
0
785245841
691421476
605409472
479058444
371688030
303203698
493383271
919185207
910180170
919185207
121535083
181713164
181713164
181713164
181...

result:

ok 577632 lines

Extra Test:

score: 0
Extra Test Passed