QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#57668#4387. Static Query on Treeqinjianbin#AC ✓153ms31700kbC++8.2kb2022-10-22 16:40:312022-10-22 16:40:35

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-22 16:40:35]
  • 评测
  • 测评结果:AC
  • 用时:153ms
  • 内存:31700kb
  • [2022-10-22 16:40:31]
  • 提交

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