QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#174752#7103. Red Black TreefryanCompile Error//C++114.0kb2023-09-10 13:05:032023-09-10 13:05:03

Judging History

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

  • [2023-09-10 13:05:03]
  • 评测
  • [2023-09-10 13:05:03]
  • 提交

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=1e7;
const int K=25;
int lg[MAXN+1];
int st[K + 1][MAXN];

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.resize(n);
	for (int i=0; i<n; i++) red[i]=0;
	adj.resize(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.resize(n);
	rd.resize(n);
	fa.resize(n);
	la.resize(n);
	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<<endl;
	}
}

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;
}

Details

/tmp/cc840sco.o: in function `_GLOBAL__sub_I_lg':
answer.code:(.text.startup+0x1e1): relocation truncated to fit: R_X86_64_PC32 against `.bss'
collect2: error: ld returned 1 exit status