QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#174616#7103. Red Black TreefryanTL 1ms3628kbC++205.4kb2023-09-10 11:13:312023-09-10 11:13:32

Judging History

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

  • [2023-09-10 11:13:32]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3628kb
  • [2023-09-10 11:13:31]
  • 提交

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> >
//constants
const int MOD=998244353;
const int INF=922337203685477580;
//nt functions
int binpow(int a, int b, int m=MOD) {
    a%=m; int res=1;
    while (b>0) {
        if (b&1) res=res*a%m;
        a=a*a%m;
        b>>=1;
    }
    return res;
}
int gcd (int a, int b) {
    return b?gcd (b,a%b):a;
}
int lcm (int a, int b) {
    return a/gcd(a,b)*b;
}
int inv(int i, int m=MOD) {
	return binpow(i, m-2, m);
}
//new header wip
struct tree {
	int n;
	vector<vector<int> > adj;
	vector<vector<int> > jump;
	vector<int> t1,t2; int t;
	tree() {}
	tree(vector<pair<int,int> > edges) {
		n=edges.size()+1;
		adj=vector<vector<int> >(n);
		for (auto i:edges) {
			adj[i.first].push_back(i.second);
			adj[i.second].push_back(i.first);
		}
		t1=vector<int>(n); t2=vector<int>(n);
		t=0; jump=vector<vector<int> >(n,vector<int>(ceil(log2(n))+1));
		dfs(0,0);
	}
	void dfs(int v, int p) {
		t1[v]=++t;
		jump[v][0]=p;
		for (int i=1; i<=ceil(log2(n)); i++) {
			jump[v][i]=jump[jump[v][i-1]][i-1];
		}
		for (auto u:adj[v]) {
			if (u!=p) dfs(u,v);
		}
		t2[v]=++t;
	}
	bool ancestor(int u, int v) {
		return t1[u]<=t1[v] && t2[u]>=t2[v];
	}
	int lca(int u, int v) {
		if (ancestor(u,v)) return u;
		if (ancestor(v,u)) return v;
		for (int i=ceil(log2(n)); i>=0; --i) {
			if (!ancestor(jump[u][i],v)) u=jump[u][i];
		}
		return jump[u][0];
	}
};

struct wtree {
	tree t;
	int n;
	vector<vector<pair<int,int> > > adj;
	vector<int> depth;
	wtree() {}
	wtree(vector<pair<pair<int,int>,int> > wedges) {
		n=wedges.size()+1;
		adj=vector<vector<pair<int,int> > >(n);
		vector<pair<int,int> > edges;
		for (auto i:wedges) {
			adj[i.first.first].push_back(make_pair(i.first.second,i.second));
			adj[i.first.second].push_back(make_pair(i.first.first,i.second));
			edges.push_back(i.first);
		}
		depth=vector<int>(n);
		t=tree(edges);
		dfs(0,0,0);
	}
	void dfs(int v, int p, int d) {
		depth[v]=d;
		for (auto i:adj[v]) {
			if (i.first==p) continue;
			dfs(i.first,v,d+i.second);
		}
	}
	int lca(int u, int v) {
		return t.lca(u,v);
	}
	int dist(int u, int v) {
		return depth[u]+depth[v]-2*depth[lca(u,v)];
	}
	int adist(int v, int p) {
		return depth[v]-depth[p];
	}
};

int n,m,q;
v2i adj;
vb red;
wtree t;
vi rd;
vi qv;

void dfs(int v, int p, int r) {
	if (red[v]) {rd[v]=0;}
	else {
		rd[v]=t.adist(v,r);
	}
	for (auto i:adj[v]) {
		if (i==p) continue;
		if (red[v]) {
			dfs(i,v,v);
		} else {
			dfs(i,v,r);
		}
	}
}

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=t.lca(clca,bad[i]);
	}
	for (auto i:bad) {
		if (t.adist(i,clca)>x) return false;
	}
	return true;
}

void solve() {
	cin>>n>>m>>q;
	red=vb(n,0);
	adj=v2i(n,vi());
	for (int i=0; i<m; i++) {
		int x; cin>>x; x--; red[x]=1;
	}
	V<P<pi,int> > edg;
	for (int i=1; i<n; i++) {
		int u,v,w; cin>>u>>v>>w;
		u--; v--; edg.pb(mp(mp(u,v),w));
		adj[u].pb(v); adj[v].pb(u);
	}
	t=wtree(edg);
	rd=vi(n);
	dfs(0,0,0);
	
	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);
	
	int t; cin>>t;
	while (t--) solve();
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3628kb

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
Time Limit Exceeded

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: