QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#73286#4387. Static Query on TreepoiTL 0ms0kbC++2.7kb2023-01-23 14:52:202023-01-23 14:52:22

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-23 14:52:22]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-01-23 14:52:20]
  • 提交

answer

#include "iostream"
#include "cstring"
#include "cstdio"
#include "algorithm"
#include "queue"
#include "vector"
#include "queue"
#include "stack"
#include "ctime"
#include "set"
#include "map"
#include "cmath"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
typedef long long ll;
const int MAXN = 2e5 + 10;
int n , q;

vi G[MAXN];

int dep[MAXN] , dfn[MAXN] , clo , R[MAXN];
int g[MAXN][20];
void dfs( int u ) {
	dfn[u] = ++ clo;
	for( int v : G[u] ) {
		dep[v] = dep[u] + 1;
		g[v][0] = u;
		rep( k , 1 , 17 ) g[v][k] = g[g[v][k - 1]][k - 1];
		dfs( v );
	}
	R[u] = clo;
}
int lca( int u , int v ) {
	if( dep[u] < dep[v] ) swap( u , v );
	per( k , 17 , 0 ) if( dep[g[u][k]] >= dep[v] ) u = g[u][k];
	if( u == v ) return u;
	per( k , 17 , 0 ) if( g[u][k] != g[v][k] ) u = g[u][k] , v = g[v][k];
	return g[u][0];
}

vi V[MAXN];

int A[MAXN] , B[MAXN] , C[MAXN];

int oc , sa[MAXN] , sb[MAXN] , res;
void afs( int u , int f ) {
	if( C[u] ) ++ oc;
	sa[u] = A[u] , sb[u] = B[u];
	for( int v : G[u] ) afs( v , u ) , sa[u] += sa[v] , sb[u] += sb[v];
	if( sa[u] && sb[u] && oc ) ++ res;
	if( C[u] ) -- oc;
	if( oc && sa[u] && sb[u] ) res += dep[u] - dep[f] - 1;
}

void solve() {
	cin >> n >> q;
	rep( i , 2 , n ) {
		int f;
		scanf("%d",&f);
		G[f].pb( i );
	}
	dep[1] = 1 , dfs( 1 );
	rep( i , 1 , q ) {
		int a , b , c , u;
		scanf("%d%d%d",&a,&b,&c);
		vi vec;
		rep( k , 1 , a ) scanf("%d",&u) , A[u] = 1 , vec.pb( u );
		rep( k , 1 , b ) scanf("%d",&u) , B[u] = 1 , vec.pb( u );
		rep( k , 1 , c ) scanf("%d",&u) , C[u] = 1 , vec.pb( u );
		vec.pb( 1 );
		sort( all( vec ) , [&]( int u , int v ) { return dfn[u] < dfn[v]; } );
		rep( t , 1 , vec.size() - 1 ) vec.pb( lca( vec[t] , vec[t - 1] ) );
		sort( all( vec ) , [&]( int u , int v ) { return dfn[u] < dfn[v]; } );
		vi stk;
		rep( t , 0 , vec.size() - 1 ) {
			while( stk.size() && R[stk.back()] < dfn[vec[t]] ) stk.pop_back();
			if( stk.size() ) V[stk.back()].pb( vec[t] );
			stk.pb( vec[t] );
		}
		oc = res = 0;
		afs( 1 , 1 );
		printf("%d\n",res);
		for( int x : vec ) A[x] = B[x] = C[x] = sa[x] = sb[x] = 0 , V[x].clear();
	}
	clo = 0;
	rep( i , 1 , n ) mem( g[i] ) , G[i].clear();
}

signed main() {
//	freopen("in","r",stdin);
//	freopen("out","w",stdout);
	int T;cin >> T;while( T-- ) solve();
//	solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

1
200000 18309
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...

output:


result: