QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#73286 | #4387. Static Query on Tree | poi | TL | 0ms | 0kb | C++ | 2.7kb | 2023-01-23 14:52:20 | 2023-01-23 14:52:22 |
Judging History
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 ...