QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#174828#7103. Red Black TreefryanAC ✓1796ms69732kbC++204.0kb2023-09-10 13:46:252023-09-10 13:46:26

Judging History

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

  • [2023-09-10 13:46:26]
  • 评测
  • 测评结果:AC
  • 用时:1796ms
  • 内存:69732kb
  • [2023-09-10 13:46:25]
  • 提交

answer

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfenv>
#include <cfloat>
#include <chrono>
#include <cinttypes>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <immintrin.h>
#include <initializer_list>
#include <iomanip>
#include <ios>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <streambuf>
#include <string>
#include <tuple>
#include <type_traits>
#include <variant>
using namespace std;
//numbers
using ll=long long;
#define int ll
using ld=long double;
//pairs
#define P pair
#define pi P<int,int>
#define ff first
#define ss second
#define mp make_pair
//std data structure
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
//vectors
#define V vector
#define vi V<int>
#define v2i V<vi>
#define v3i V<v2i>
#define vpi V<pi>
#define vsi V<si>
#define vb V<bool>
#define pb push_back
//sets
#define S set
#define MS multiset
#define US unordered_set
#define si S<int>
#define msi MS<int>
#define usi US<int>
#define ins insert
#define era erase
//maps
#define M map
#define UM unordered_map
#define mii M<int,int>
#define mivi UM<int,vi>
#define misi UM<int,si>
#define umii UM<int,int>
#define umivi UM<int,vi>
#define umisi UM<int,si>
//queues
#define Q queue
#define PQ priority_queue
#define qi Q<int>
#define qpi Q<pi>
#define pqi PQ<int>
#define rpqi PQ<int,vi,greater<int> >
#define pqpi PQ<pi>
#define rpqpi PQ<pi,vpi,greater<pi> >
#define rep(i, a, b) for(int i = a; i < (b); ++i)
//constants
const int MOD=998244353;
const int INF=922337203685477580;
const int MAXN=2e5;
const int K=25;
vi lg(2e5);
v2i st(K+1,vi(2e5));

vi depth;

int comb(int a, int b) {
	if (depth[a]<depth[b]) return a;
	return b;
}

int n,m,q;
V<vpi> adj;
vb red;
vi rd;
vi qv;
vi tour;
vi fa;
vi la;
vi ke;

void dfs(int v, int p, int r, int d) {
	depth[v]=d;
	fa[v]=sz(tour);
	tour.pb(v);
	if (red[v]) {rd[v]=0;}
	else {rd[v]=r;}
	for (auto i:adj[v]) {
		if (i.ff==p) continue;
		dfs(i.ff,v,rd[v]+i.ss,d+i.ss);
		la[v]=sz(tour);
		tour.pb(v);
	}
}

int lca(int u, int v) {
	if (fa[v]<fa[u]) swap(u,v);
	int L=fa[u]; int R=fa[v];
	int i = lg[R - L + 1];
	return comb(st[i][L], st[i][R - (1 << i) + 1]);
}

bool verif(int x) {
	vi bad;
	for (auto i:qv) {
		if (rd[i]>x) {
			bad.pb(i);
		}
	}
	if (sz(bad)<2) return true;
	int clca=bad[0];
	for (int i=1; i<sz(bad); i++) {
		clca=lca(clca,bad[i]);
	}
	for (auto i:bad) {
		if (depth[i]-depth[clca]>x) return false;
	}
	return true;
}

void solve() {
	cin>>n>>m>>q; red=vb(n,0);
	for (int i=0; i<n; i++) red[i]=0;
	adj=V<vpi>(n);
	for (int i=0; i<n; i++) adj[i]=vpi();
	for (int i=0; i<m; i++) {
		int x; cin>>x; x--; red[x]=1;
	}
	for (int i=1; i<n; i++) {
		int u,v,w; cin>>u>>v>>w; u--; v--;
		adj[u].pb(mp(v,w)); adj[v].pb(mp(u,w));
	}
	depth=vi(n);
	rd=vi(n);
	fa=vi(n);
	la=vi(n);
	tour.clear();
	dfs(0,0,0,0);
	
	for (int i=0; i<sz(tour); i++) {
		st[0][i]=tour[i];
	}
	for (int i = 1; i <= K; i++)
    	for (int j = 0; j + (1 << i) <= sz(tour); j++)
    		st[i][j] = comb(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
	
	while (q--) {
		int k; cin>>k;
		qv=vi(k);
		for (int i=0; i<k; i++) {cin>>qv[i];qv[i]--;}
		int lo=0;
		int hi=INF;
		while (lo<=hi) {
			int mid=(lo+hi)/2;
			if (verif(mid)) {hi=mid-1;}
			else {lo=mid+1;}
		}	
		cout<<lo<<"\n";
	}
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	lg[1] = 0;
	for (int i = 2; i <= MAXN; i++) lg[i] = lg[i/2] + 1;
	int t; cin>>t;
	while (t--) solve();
	
	return 0;
}

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

详细

Test #1:

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

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: 1796ms
memory: 69732kb

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