QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#57668 | #4387. Static Query on Tree | qinjianbin# | AC ✓ | 153ms | 31700kb | C++ | 8.2kb | 2022-10-22 16:40:31 | 2022-10-22 16:40:35 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<bitset>
using namespace std;
//STL库常用(vector, map, set, pair)
#define pii pair<int,int>
#define pdd pair<double,double>
#define F first
#define S second
//常量
#define PI (acos(-1.0))
#define INF 0x3f3f3f3f
//必加
#ifdef TanJI
#include<cassert>
#define dbg(...) do {cerr << "\033[33;1m" << #__VA_ARGS__ << " -> "; err(__VA_ARGS__); } while(0)
void err() {cerr << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A> void err(T<t> a, A... x) {for (auto v: a) cerr << v << ' '; cerr << ", "; err(x...);}
template<typename T, typename... A> void err(T a, A... x) {cerr << a << ' '; err(x...);}
template<typename T> void err(T *a, int len) {for (int i = 0; i < len; i++) cerr << a[i] << ' '; err();}
#else
#define dbg(...)
#define assert(...)
#endif
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
// 快读快输
template<typename T> inline T read() {T x=0; bool f=0; char c=getchar();while(!isdigit(c)){if(c =='-')f= 1; c=getchar();}while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return f?~x+1:x;}
template<typename T> inline void print(T k){ int num = 0,ch[20]; if(k == 0){ putchar('0'); return ; } (k<0)&&(putchar('-'),k = -k); while(k>0) ch[++num] = k%10, k /= 10; while(num) putchar(ch[num--]+48); }
//图论
const int GRAPHN = 1, GRAPHM = 1;
/*int h[GRAPHN], e[GRAPHM], ne[GRAPHM], wei[GRAPHM], idx;
void AddEdge(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;}
void AddEdge(int a, int b, int c) {e[idx] = b, ne[idx] = h[a], wei[idx] = c, h[a] = idx++;}
void AddEdge(int h[], int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;}
void AddEdge(int h[], int a, int b, int c) {e[idx] = b, ne[idx] = h[a], wei[idx] = c, h[a] = idx++;}
*/
// 数学公式
template<typename T> inline T gcd(T a, T b){ return b==0 ? a : gcd(b,a%b); }
template<typename T> inline T lowbit(T x){ return x&(-x); }
template<typename T> inline bool mishu(T x){ return x>0?(x&(x-1))==0:false; }
template<typename T1,typename T2, typename T3> inline ll q_mul(T1 a,T2 b,T3 p){ ll w = 0; while(b){ if(b&1) w = (w+a)%p; b>>=1; a = (a+a)%p; } return w; }
template<typename T,typename T2> inline ll f_mul(T a,T b,T2 p){ return (a*b - (ll)((long double)a/p*b)*p+p)%p; }
template<typename T1,typename T2, typename T3> inline ll q_pow(T1 a,T2 b,T3 p){ ll w = 1; while(b){ if(b&1) w = (w*a)%p; b>>=1; a = (a*a)%p;} return w; }
template<typename T1,typename T2, typename T3> inline ll s_pow(T1 a,T2 b,T3 p){ ll w = 1; while(b){ if(b&1) w = q_mul(w,a,p); b>>=1; a = q_mul(a,a,p);} return w; }
template<typename T> inline ll ex_gcd(T a, T b, T& x, T& y){ if(b == 0){ x = 1, y = 0; return (ll)a; } ll r = ex_gcd(b,a%b,y,x); y -= a/b*x; return r;/*gcd*/ }
template<typename T1,typename T2> inline ll com(T1 m, T2 n) { int k = 1;ll ans = 1; while(k <= n){ ans=((m-k+1)*ans)/k;k++;} return ans; }
template<typename T> inline bool isprime(T n){ if(n <= 3) return n>1; if(n%6 != 1 && n%6 != 5) return 0; T n_s = floor(sqrt((db)(n))); for(int i = 5; i <= n_s; i += 6){ if(n%i == 0 || n%(i+2) == 0) return 0; } return 1; }
/* ----------------------------------------------------------------------------------------------------------------------------------------------------------------- */
const int MAXN = 2e5 + 10;
int T;
int n,q;
struct edgeType{
int to,nxt;
}e[MAXN];
int head[MAXN];
int act[MAXN][20];
int dfn[MAXN];
int cntD;
int depth[MAXN];
void add_edge(int u,int v,int x)
{
e[x].to=v;
e[x].nxt=head[u];
head[u]=x;
}
void dfs(int x)
{
int i;
depth[x]=depth[act[x][0]]+1;
dfn[x]=++cntD;
for(i=1;act[act[x][i-1]][i-1];i++)
act[x][i]=act[act[x][i-1]][i-1];
for(i=head[x];i;i=e[i].nxt)
dfs(e[i].to);
}
void standing_by()
{
int i;
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++) head[i]=0;
for(i=2;i<=n;i++)
{
scanf("%d",&act[i][0]);
add_edge(act[i][0],i,i-1);
}
cntD=0;
dfs(1);
}
int get_lca(int x,int y)
{
if (x==y) return x;
if (depth[x]>depth[y]) swap(x,y);
int i;
for(i=19;i>=0;i--)
if (depth[act[y][i]]>=depth[x]) y=act[y][i];
if (x==y) return x;
for(i=19;i>=0;i--)
if (act[y][i]!=act[x][i])
{
y=act[y][i];
x=act[x][i];
}
return act[x][0];
}
int qhy[MAXN];
int cntQ;
bool cmp(int x,int y)
{
return dfn[x]<dfn[y];
}
struct virEdgeType
{
int to,nxt;
}ve[MAXN];
int vhead[MAXN];
int vpt[MAXN];
int cntVE;
int root;
void add_vedge(int u, int v, int x) {
ve[x].to = v;
ve[x].nxt = vhead[u];
vhead[u] = x;
}
int stk[MAXN],sTop;
bool eA[MAXN],eB[MAXN],eC[MAXN];
int ans=0;
void vdfs(int x,bool theC)
{
int i;
for(i=vhead[x];i;i=ve[i].nxt)
{
vdfs(ve[i].to,theC|eC[x]);
eA[x]|=eA[ve[i].to];
eB[x]|=eB[ve[i].to];
}
if (eA[x]&&eB[x]&&theC)
ans+=depth[x]-depth[vpt[x]]-1;
if (eA[x]&&eB[x]&&(theC|eC[x]))
ans++;
}
void clear(int x)
{
int i;
for (i = vhead[x]; i; i = ve[i].nxt) {
clear(ve[i].to);
}
eA[x]=eB[x]=eC[x]=0;
vhead[x]=vpt[x]=0;
}
void complete()
{
int i,j,k;
int a,b,c;
int x;
for(;q;q--)
{
scanf("%d%d%d",&a,&b,&c);
cntQ=0;
for(i=1;i<=a;i++)
{
scanf("%d",&x);
if (!eA[x]&&!eB[x]&&!eC[x])
qhy[++cntQ]=x;
eA[x]=true;
}
for (i = 1; i <= b; i++) {
scanf("%d", &x);
if (!eA[x] && !eB[x] && !eC[x])
qhy[++cntQ] = x;
eB[x] = true;
}
for (i = 1; i <= c; i++) {
scanf("%d", &x);
if (!eA[x] && !eB[x] && !eC[x])
qhy[++cntQ] = x;
eC[x] = true;
}
sort(qhy+1,qhy+1+cntQ,cmp);
//printf("%d\n",cntQ);
//for(i=1;i<=cntQ;i++) printf("%d ",qhy[i]);
//puts("");
cntVE=0;
sTop=0;
int tmpLCA;
for (i = 1; i <= cntQ; i++) {
if (sTop==0)
{
stk[++sTop]=qhy[i];
}else {
tmpLCA=get_lca(stk[sTop],qhy[i]);
//printf("%d %d %d\n",stk[sTop],qhy[i],tmpLCA);
for(;sTop>=2&&depth[stk[sTop-1]]>=depth[tmpLCA];sTop--)
{
add_vedge(stk[sTop-1],stk[sTop],++cntVE);
vpt[stk[sTop]]=stk[sTop-1];
}
if (tmpLCA==stk[sTop])
{
stk[++sTop]=qhy[i];
}else if (depth[tmpLCA]>depth[stk[sTop]]){
stk[++sTop] = tmpLCA;
stk[++sTop]=qhy[i];
}else {
add_vedge(tmpLCA,stk[sTop],++cntVE);
vpt[stk[sTop]]=tmpLCA;
sTop--;
stk[++sTop] = tmpLCA;
stk[++sTop] = qhy[i];
}
}
//printf("%d\n",sTop);
// for(int j=1;j<=sTop;j++) printf("%d ",stk[j]);
// puts("");
}
for(;sTop>1;sTop--)
{
add_vedge(stk[sTop - 1], stk[sTop], ++cntVE);
vpt[stk[sTop]] = stk[sTop - 1];
}
//for (i = 1; i <= n; i++)
// printf("%d %d\n", i, vpt[i]);
root=stk[1];
ans=0;
vdfs(root,false);
printf("%d\n",ans);
clear(root);
}
}
int main() {
#ifdef TanJI
clock_t c1 = clock();
freopen("D:\\Cpp\\1.in", "r", stdin);
freopen("D:\\Cpp\\1.out", "w", stdout);
#endif
//--------------------------------------------
scanf("%d", &T);
while (T--) {
standing_by();
complete();
}
//--------------------------------------------
#ifdef TanJI
cerr << "Time Used:" << clock() - c1 << "ms" << endl;
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 153ms
memory: 31700kb
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:
102147 62590 87270 88880 7654 61542 62953 85022 55135 54125 70500 64356 25824 88300 42278 15336 18132 28734 90282 42889 28099 31311 96842 19959 34366 60205 78358 91142 56048 74688 86091 51979 94750 11989 89544 86860 56720 29534 52343 90031 79002 90293 94554 48340 65015 9181 15016 19884 49445 14181 6...
result:
ok 18309 numbers