QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#57626	#4387. Static Query on Tree	qinjianbin^#	WA	177ms	32148kb	C++	8.2kb	2022-10-22 16:03:43	2022-10-22 16:04:32

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:04:32]
评测

测评结果：WA
用时：177ms
内存：32148kb

查看

[2022-10-22 16:03:43]
提交

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 (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]&&eC[x])
        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;
}

源文件, 语言: C++

詳細信息

Test #1:

score: 0

Wrong Answer

time: 177ms

memory: 32148kb

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:

wrong answer 1st numbers differ - expected: '102147', found: '73229'