QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #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
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;
}
Details
Tip: Click on the bar to expand more detailed information
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:
73229 5 6 3 3 7 7 2 8 5 4 7 3 6 6 2 2 2 7 3 4 3 7 3 2 5 6 6 6 6 4 4 3 3 5 5 2 3 3 5 8 2 5 5 6 2 3 4 3 3 5 3 6 6 5 5 4 3 7 2 4 7 5 2 4 4 3 4 4 2 7 5 5 5 4 4 5 3 2 5 8 5 4 2 7 6 2 4 2 3 6 7 5 2 3 7 5 4 2 3 2 5 5 5 5 7 4 4 3 5 5 2 5 2 2 6 2 5 4 8 4 3 4 6 2 6 3 8 3 4 2 3 6 3 5 4 7 4 4 5 6 4 2 3 5 6 3 3 ...
result:
wrong answer 1st numbers differ - expected: '102147', found: '73229'