QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#405654 | #8630. 字符树 | dingdingtang11514# | 10 | 24ms | 124588kb | C++14 | 6.7kb | 2024-05-06 11:41:00 | 2024-05-06 11:41:00 |
Judging History
answer
#include <iostream>
#include <cstring>
#include <map>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <set>
// #include <bits/stdc++.h>
// #define int long long
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
#define Grf(it,u,to) for(int it=he[u],to;(to=e[it],it);it=nxt[it])
#define In __inline
#define OP operator
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
namespace Mine {
// mt19937_64 wql(514);
In int read() {
ll x=1,a=0;
char ch=getchar();
while(ch>'9' || ch<'0') x=(ch=='-')?-1:x,ch=getchar();
while(ch>='0' && ch<='9') a=(a<<1)+(a<<3)+(ch-'0'),ch=getchar();
return a*x;
} const int N=5e5+100;
char ch[N];int n,m,X,fa[N],f[N][21],dep[N];
bool No1=1;
In int lca(int x,int y) {
if(dep[x]<dep[y]) swap(x,y);
Rof(i,20,0) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
if(x==y) return x;
Rof(i,20,0) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
} int he[N],nxt[N],cf[N],idx=1,e[N];
void adde(int a,int b,int c) {
e[++idx]=b,cf[idx]=c,nxt[idx]=he[a];he[a]=idx;
}
namespace sol {
namespace Mine {
// mt19937_64 wql(514);
In ll read() {
ll x=1,a=0;
char ch=getchar();
while(ch>'9' || ch<'0') x=(ch=='-')?-1:x,ch=getchar();
while(ch>='0' && ch<='9') a=(a<<1)+(a<<3)+(ch-'0'),ch=getchar();
return a*x;
} const int N=1e6+100;
struct ACAM {
int son[N][26],fail[N],idx=0,tr[N],dfn[N],ed[N],tot;
vector<int> fs[N];
void dfs(int u) {
dfn[u]=++tot; for(int to:fs[u]) {dfs(to);} ed[u]=tot;
} void build() {
queue<int> q; For(i,0,25) if(son[0][i]) q.push(son[0][i]);
while(q.size()) { int u=q.front();q.pop();
// printf("%d\n",u);
For(i,0,25) {
if(!son[u][i]) son[u][i]=son[fail[u]][i];
else fail[son[u][i]]=son[fail[u]][i],q.push(son[u][i]);
}
} For(i,1,idx) fs[fail[i]].push_back(i);
// For(i,0,idx) {for(int j:{'w'-'a','x'-'a'}) printf("%d ",son[i][j]);puts("");}puts("");
dfs(0); //For(i,0,idx) printf("%d ",dfn[i]);
// puts("");For(i,0,idx) printf("%d ",fail[i]);puts("");
} void mdf(int pos,int val) {for(;pos<=tot;pos+=pos&-pos) tr[pos]+=val;}
In int qry(int pos) {int ret=0; for(;pos;pos-=pos&-pos){ret+=tr[pos];}return ret;}
In int get(int u) {return qry(ed[u])-qry(dfn[u]-1);}
} A1,A2;int he[N],nxt[N<<1],e[N<<1],n,m; char w[N<<1];
namespace E {int idx=1; void adde(int a,int b,char d) {e[++idx]=b,w[idx]=d,nxt[idx]=he[a],he[a]=idx;}}
using E::adde; struct node { int qid,val; } ; vector<node> b1[N],b2[N];
int fa[N][23],dep[N];char from[N]; void get_fa(int u,int f) {
dep[u]=dep[f]+1;fa[u][0]=f; For(i,1,22) fa[u][i]=fa[fa[u][i-1]][i-1];
Grf(it,u,to) {if(to!=f) {from[to]=w[it];get_fa(to,u);}}
} In int lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y);
Rof(i,22,0) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
if(x==y) return x;
Rof(i,22,0) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
} struct Que {int x,y,top,a,b,ans;} q[N];
char S[N];int ls; In int FA(int u,int x) {Rof(i,19,0) {if(x>=(1<<i))x-=(1<<i),u=fa[u][i];}return u;}
char ch[N],lch; In int kmp() {
static int nxt[N];
// printf("%s ",ch+1,S);
nxt[1]=0; int j=0; For(i,2,ls) {
while(j && S[j+1]!=S[i]) j=nxt[j];
if(S[j+1]==S[i]) j++;
nxt[i]=j;
} int ret=0; j=0; For(i,1,lch) {
while(j && S[j+1]!=ch[i]) j=nxt[j];
if(S[j+1]==ch[i]) j++;
if(j==ls) ret++,j=nxt[j];
} return ret;
} void dfs(int u,int ff,int r1,int r2) {
A1.mdf(A1.dfn[r1],1);A2.mdf(A2.dfn[r2],1);
for(auto &j:b1[u]) q[j.qid].ans+=j.val*A1.get(q[j.qid].a);
for(auto &j:b2[u]) q[j.qid].ans+=j.val*A2.get(q[j.qid].b);
Grf(it,u,to) if(to!=ff) dfs(to,u,A1.son[r1][w[it]-'a'],A2.son[r2][w[it]-'a']);
A1.mdf(A1.dfn[r1],-1);A2.mdf(A2.dfn[r2],-1);
} signed main() {
get_fa(1,0);
For(i,1,m) {
int opt=read(); if(opt==1) No1=0;
q[i].x=read();q[i].y=read();q[i].top=lca(q[i].x,q[i].y);
// printf("%d %d %d\n",q[i].x,q[i].y,q[i].top);
scanf("%s",S+1);ls=strlen(S+1);int u=0; For(i,1,ls) {
int &to=A1.son[u][S[i]-'a']; if(!to) to=++A1.idx;
u=to;
}q[i].a=u; u=0; Rof(i,ls,1) {
int &to=A2.son[u][S[i]-'a']; if(!to) to=++A2.idx;
u=to;
}q[i].b=u; if(q[i].x!=q[i].top && q[i].y!=q[i].top) {
int b=min(ls-1,dep[q[i].x]-dep[q[i].top]);lch=b;
for(int a=1,j=FA(q[i].x,dep[q[i].x]-dep[q[i].top]-b);j!=q[i].top;j=fa[j][0],a++) ch[a]=from[j];
b=min(ls-1,dep[q[i].y]-dep[q[i].top]);lch+=b;
for(int a=lch,j=FA(q[i].y,dep[q[i].y]-dep[q[i].top]-b);j!=q[i].top;j=fa[j][0],a--) ch[a]=from[j];
q[i].ans=kmp();
}
if(dep[q[i].x]-dep[q[i].top]>=ls)
b2[q[i].x].push_back((node){i,1}),b2[FA(q[i].x,dep[q[i].x]-dep[q[i].top]-ls+1)].push_back((node){i,-1});
if(dep[q[i].y]-dep[q[i].top]>=ls)
b1[q[i].y].push_back((node){i,1}),b1[FA(q[i].y,dep[q[i].y]-dep[q[i].top]-ls+1)].push_back((node){i,-1});
} A1.build(),A2.build(); dfs(1,0,0,0);
For(i,1,m) printf("%d\n",q[i].ans);
return 0;
}
} using namespace Mine;
}
char rd[N];
namespace S0 {
int ch[N],lch,S[N],ls;
In int kmp() {
static int nxt[N];
nxt[1]=0; int j=0; For(i,2,ls) {
while(j && S[j+1]!=S[i]) j=nxt[j];
if(S[j+1]==S[i]) j++;
nxt[i]=j;
} int ret=0; j=0; For(i,1,lch) {
while(j && S[j+1]!=ch[i]) j=nxt[j];
if(S[j+1]==ch[i]) j++;
if(j==ls) ret++,j=nxt[j];
} return ret;
}
void solve0() {
while(m--) {
int opt=read(),x=read(),y=read();scanf("%s",rd+1);
For(i,1,X) S[i]=rd[i]-'0';
int p=lca(x,y);//printf("P: %d\n",dep[p]);
if(opt==1) {int pos=1;
while(x!=p) cf[x]=S[pos++],x=fa[x];
pos=X;
while(y!=p) cf[y]=S[pos--],y=fa[y];
} else { lch=0;ls=X;
while(x!=p) ch[++lch]=cf[x],x=fa[x];
int pos=lch+dep[y]-dep[p];lch+=dep[y]-dep[p];
// printf("POS %d\n",pos);
while(y!=p) ch[pos--]=cf[y],y=fa[y];
// For(i,1,lch) printf("%d ",ch[i]);
// puts("");
printf("%d\n",kmp());
}
}
}
}
signed main() {
n=read(),m=read(),X=read();
For(i,2,n) f[i][0]=fa[i]=read();
For(i,1,n) {dep[i]=dep[fa[i]]+1;For(j,1,20) f[i][j]=f[f[i][j-1]][j-1];}
scanf("%s",rd+1);
For(i,2,n) {adde(fa[i],i,rd[i-1]-'0');}
if(n<=250 && m<=250) S0::solve0();
else {
For(i,2,n) sol::adde(i,fa[i],cf[i]+'0'),sol::adde(fa[i],i,cf[i]+'0');
sol::n=n,sol::m=m;
sol::main();
}
return 0;
}
}signed main() {
// freopen("homework.in","r",stdin);
// freopen("homework.out","w",stdout);
return Mine::main();
}
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 16ms
memory: 124588kb
input:
250 250 62 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 30 67 68 8 70 16 72 3 74 75 32 77 75 31 80 81 65 83 30 19 49 4 1 89 57 91 92 43 94 95 96 85 51 32 100 8...
output:
1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 2 3 0 0 0 4 4 0 0 0 0 0 2 0 4 0 0 0 0 0 0 0 0 4 0 0 0 0 1 0 0 10 0 0 0 0 0 0 2 0 0 0 0 0 0 0 3 0 2 0 1 0 0 7
result:
ok 118 numbers
Test #2:
score: 10
Accepted
time: 11ms
memory: 118440kb
input:
250 250 6 1 1 1 4 1 1 1 1 1 1 1 1 1 14 1 1 1 1 19 1 1 1 1 24 1 26 27 28 1 30 1 32 1 1 35 1 37 1 1 1 1 1 43 44 45 1 47 1 1 1 1 1 53 54 1 56 57 58 1 60 1 62 63 64 65 1 1 68 69 70 71 1 1 1 1 76 77 78 79 1 81 1 83 84 1 1 1 88 89 1 91 1 93 94 1 96 97 98 99 1 1 102 103 1 105 106 107 108 1 110 111 112 113 ...
output:
1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1 1 0 1 0 0 1 0 0 0 3 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 3 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 2 2 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 1 0 1
result:
ok 118 numbers
Test #3:
score: 10
Accepted
time: 7ms
memory: 120764kb
input:
250 250 6 1 2 2 4 5 2 7 2 8 10 11 12 13 14 14 16 17 16 19 20 21 22 1 24 16 26 27 28 29 23 31 20 33 34 35 15 37 38 39 40 41 42 30 44 45 46 47 32 49 50 34 52 53 54 7 56 9 58 59 60 52 42 63 64 65 43 67 68 69 70 71 72 11 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 20 66 95 96 97 9 99 100 10...
output:
0 1 1 1 2 1 0 0 8 1 1 0 0 1 1 2 3 1 1 1 1 3 1 0 1 2 0 2 0 8 1 0 2 1 0 2 1 1 3 0 0 1 0 1 0 1 0 0 1 0 2 0 0 3 0 0 0 3 2 0 3 0 5 0 13 5 0 0 7 4 1 0 0 0 1 0 3 0 0 7 0 0 6 0 9 3 8 0 3 7 7 0 15 1 0 8 0 1 6 10 10 0 2 1 0 0 0 3 0 2 6 3 0 3 0 0 2 7 2 0 2 6 17 2 0 0 0 0 0
result:
ok 129 numbers
Test #4:
score: 10
Accepted
time: 12ms
memory: 124580kb
input:
246 250 113 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 99 ...
output:
1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 6 1 0 1 0 2 0 2 1 1 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 1 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 128 numbers
Test #5:
score: 10
Accepted
time: 15ms
memory: 122548kb
input:
249 250 47 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 1 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 1 1 70 71 1 73 74 75 76 1 78 1 80 1 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 1 99 1 101 1 1...
output:
1 1 1 1 0 1 0 1 0 0 0 1 1 0 1 1 0 1 1 1 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 118 numbers
Test #6:
score: 10
Accepted
time: 24ms
memory: 120760kb
input:
250 250 95 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 14 5 98 99 5 ...
output:
1 1 1 1 0 1 1 0 0 1 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0
result:
ok 121 numbers
Test #7:
score: 10
Accepted
time: 8ms
memory: 122496kb
input:
250 245 12 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 26 27 28 29 1 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 1 49 50 51 52 53 1 55 56 57 1 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 1 80 81 82 83 84 85 86 87 88 89 1 91 92 93 94 95 96 97 98 1 100 101 1...
output:
1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 4 0 4 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 9 0 0 1 0 0 1 4 0 0 4 0 1 0 0 0 0 2 1 9 0 0 0 7 0 0 2 0 0 0 0 0 0 4 11 0 0 0 0 11 19 1 2 0 0 0 0 0 4 0 0
result:
ok 123 numbers
Test #8:
score: 10
Accepted
time: 8ms
memory: 122604kb
input:
250 250 82 1 1 1 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 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 99 10...
output:
1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 49 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 22 0 0 0 0 0 0 0 0 0 0 0 0 36 0 0 18 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
result:
ok 118 numbers
Test #9:
score: 10
Accepted
time: 8ms
memory: 122788kb
input:
250 250 7 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 33 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 26 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...
output:
1 1 0 0 1 0 1 1 1 1 0 1 1 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 1 0 1 1 1 1 1 0 1 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 3 0 0 0 0 3 0 8 0 6 0 7 0 10 10 10 0 0 0 0 2 0 2 0 0 0 1 0 9 0 2 17 4 1 0 0 0 0 1 0 0 0 2 0 0 1 4 3 0 0 0 0
result:
ok 123 numbers
Test #10:
score: 10
Accepted
time: 12ms
memory: 120524kb
input:
249 246 2 1 2 2 2 5 4 7 1 2 2 11 3 2 3 15 11 7 13 9 20 6 6 13 8 13 26 27 6 5 30 31 32 33 34 35 2 29 38 39 40 21 30 37 44 45 14 25 32 49 50 51 52 15 5 14 37 23 27 59 60 61 51 63 47 12 34 57 34 69 70 49 60 25 3 75 72 51 78 78 80 81 78 83 84 85 86 62 88 89 90 2 92 93 94 95 96 97 41 89 81 87 102 45 14 3...
output:
2 3 0 1 2 9 1 1 2 2 2 3 2 3 0 0 1 1 1 0 2 1 2 1 2 8 0 1 2 0 0 3 0 2 2 0 0 2 3 0 1 6 0 1 3 4 2 2 5 5 0 0 1 1 3 0 1 5 0 3 0 4 6 4 7 6 0 8 1 4 0 0 3 0 0 0 0 3 0 0 7 0 6 4 1 1 2 1 1 1 4 1 0 1 3 1 1 0 1 0 4 0 1 0 0 0 7 6 0 0 0 2 0 1 1 4 1 0 4 9 1 0 4 2 2
result:
ok 125 numbers
Subtask #2:
score: 0
Runtime Error
Test #11:
score: 0
Runtime Error
input:
500000 650 769 1 2 3 4 5 6 7 8 9 10 11 12 7 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 9...
output:
result:
Subtask #3:
score: 0
Runtime Error
Test #21:
score: 0
Runtime Error
input:
500000 499998 1 1 2 3 4 5 6 7 8 1 1 11 12 13 14 15 16 1 1 19 20 21 22 23 24 1 26 1 28 29 30 1 32 33 34 35 1 37 38 39 40 41 42 43 1 45 46 47 48 49 50 1 52 53 54 55 56 57 1 1 60 61 62 63 64 65 66 67 68 69 1 71 1 73 1 75 76 77 78 79 80 81 82 83 1 1 86 87 88 89 1 91 92 93 94 95 96 97 98 99 100 101 102 1...
output:
1 0 0 0 0 0 2 0 1 5 0 1 0 2 4 0 0 1 0 1 0 0 1 0 0 4 3 0 3 1 1 0 3 0 3 1 0 0 1 0 2 0 1 1 1 0 1 1 0 0 0 0 2 0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 2 3 2 0 1 0 0 0 0 2 4 0 1 0 0 0 3 0 1 1 3 4 0 1 0 0 0 1 0 0 0 0 0 0 0 0 3 0 0 1 1 0 0 0 3 0 0 1 1 1 0 3 6 3 2 0 0 3 0 1 1 1 1 6 1 0 0 3 1 0 1 1 0 3 0 0 3 1 3 0 ...
result:
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Runtime Error
Test #41:
score: 0
Runtime Error
input:
499997 9 40060 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:
Subtask #6:
score: 0
Runtime Error
Test #51:
score: 0
Runtime Error
input:
500000 62500 8 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:
0 0 122 0 0 489 0 134 0 0 0 0 0 0 0 0 0 28 516 0 0 0 38 0 71 0 0 0 0 0 81 0 0 149 0 0 9 0 536 0 346 0 1137 40 34 0 30 0 4 0 0 413 0 286 0 0 0 1235 0 0 104 300 0 532 0 0 0 0 123 27 0 0 0 51 442 0 66 75 68 544 0 56 33 194 0 0 0 0 0 224 0 7 0 63 9 362 407 0 5 33 0 0 27 10 0 133 174 0 0 0 0 0 1 16 51 11...
result:
Subtask #7:
score: 0
Runtime Error
Test #61:
score: 0
Runtime Error
input:
500000 100000 5 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:
2 5995 10021 58263 12720 1 70338 0 0 35483 0 30541 0 0 4346 31843 50389 21896 0 22132 1 52130 0 0 1 0 0 0 9410 0 58705 90779 1 29762 47315 74100 0 0 5730 6071 1 3931 60337 28004 0 1 0 1 17419 1996 3 0 41417 1 31204 0 12712 0 51145 0 1 0 1 9415 88632 0 1 16474 0 0 1 48315 38729 2159 13207 0 16015 1 8...
result:
Subtask #8:
score: 0
Runtime Error
Test #71:
score: 0
Runtime Error
input:
25000 2500 10 1 2 3 4 5 6 7 8 9 10 1 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 99...
output:
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 3 0 0 0 1 0 0 1 0 0 7 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 8 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 4 0 1 0 0 0 0 0 ...
result:
Subtask #9:
score: 0
Skipped
Dependency #8:
0%
Subtask #10:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%