QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #757406 | #1222. 多边形 | I_be_wanna | 100 ✓ | 1346ms | 125576kb | C++20 | 32.4kb | 2024-11-17 06:46:36 | 2024-11-17 06:46:41 |
Judging History
answer
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
map<ll,int>M;
const int N=1100,NS=2400,NL=10,mo=998244353;
struct atom{
int m;
int A[NL],d[NL];
ll h;
int totd;
void gettotd(){
totd=0;
for (int i=0;i<=m;i++) totd+=2-d[i];
}
ll gethash(){
ll k1=0;
for (int i=0;i<=m;++i) k1=1ll*k1*10+A[i];
for (int i=0;i<=m;++i) k1=1ll*k1*3+d[i];
h=k1; return k1;
}
void print(){
printf("%d\n",m);
for (int i=0;i<=m;i++) printf("%d ",A[i]); puts("");
for (int i=0;i<=m;i++) printf("%d ",d[i]); puts("");
}
void checkvalid(){
for (int i=0;i<=m;i++) if (d[i]!=2) assert(A[i]!=0); else assert(A[i]==0);
int t[20];
memset(t,0x00,sizeof t);
for (int i=0;i<=m;i++) t[A[i]]+=2-d[i];
for (int i=0;i<=m;i++) if (A[i]) assert(t[A[i]]==2);
int num=0;
for (int i=0;i<=m;i++) assert(A[i]<=num+1),num=max(num,A[i]);
}
}x[NS];
int len;
int A[NL],d[NL],t[NL];
vector<pair<int,int> >gof[NS][NS],addf[NS],allP;
int idx[NS],bo[NS],sign;
vector<int>go[N];
int n,K,m,f[N][NS],sz[N];
int addin(atom k1){
k1.gethash();
if (M[k1.h]) return M[k1.h];
assert(len+1<NS);
x[++len]=k1; M[k1.h]=len; return len;
}
int link(int *A,int *d,int u,int v,int n){
if (d[u]==2||d[v]==2||A[u]==A[v]) return 0;
d[u]++; d[v]++;
int k1=A[u],k2=A[v];
for (int i=0;i<=n;i++) if (A[i]==k1) A[i]=k2;
if (d[u]==2) A[u]=0;
if (d[v]==2) A[v]=0;
return 1;
}
int link2(int *A,int *d,int u,int v,int n){
if (d[u]==2||d[v]==2) return 0;
if (A[u]!=A[v]) return link(A,d,u,v,n);
for (int i=0;i<=n;i++)
if (d[i]<2&&A[i]!=A[u]) return 0;
d[u]++; d[v]++;
if (d[u]==2) A[u]=0;
if (d[v]==2) A[v]=0;
return 2;
}
int checkfinal(int *A,int *d,int n){
for (int i=0;i<=n;i++) if (A[i]){
assert(d[i]<2); return 0;
}
for (int i=0;i<=n;i++) assert(d[i]==2);
return 1;
}
void normalize(int *A,int n){
static int w[NL*2];
int now=0;
memset(w,0x00,sizeof w);
for (int i=0;i<=n;i++)
if (A[i]){
if (w[A[i]]) A[i]=w[A[i]];
else {
now++; w[A[i]]=now; A[i]=now;
}
}
}
atom getatom(int *A,int *d,int n){
atom res;
if (n>K*2){
for (int i=K+1;i<=n-K;i++)
if (d[i]!=2){
res.m=-1; return res;
}
int now=K;
for (int i=n-K+1;i<=n;i++){
now++; A[now]=A[i]; d[now]=d[i];
}
n=now;
}
res.m=n;
for (int i=0;i<=n;i++) res.A[i]=A[i];
for (int i=0;i<=n;i++) res.d[i]=d[i];
return res;
}
void getaddf(int k1){
static int A[NL];
static int d[NL];
int m=x[k1].m;
int now=min(K,x[k1].m);
int ma=0; sign++;
for (int i=0;i<=x[k1].m;++i)
if (x[k1].d[i]!=2) ma=max(ma,x[k1].A[i]);
for (int isl=0;isl<2;isl++){
if (isl&&x[k1].d[0]==2) continue;
for (int S=0;S<(1<<now);++S){
if (__builtin_popcount(S)>2) continue;
memcpy(A,x[k1].A,sizeof x[k1].A);
memcpy(d,x[k1].d,sizeof x[k1].d);
A[m+1]=ma+1; d[m+1]=0;
if (isl){
if (link(A,d,0,m+1,m+1)==0) continue;
}
int flag=0;
for (int i=1;i<=now;i++){
if ((S&(1<<i-1))==0) continue;
int id=x[k1].m-now+i;
if (link(A,d,id,m+1,m+1)==0){
flag=1; break;
}
}
if (flag) continue;
normalize(A,m+1);
atom res=getatom(A,d,m+1);
if (res.m==-1) continue;
res.checkvalid();
int where=addin(res);
if (bo[where]!=sign){
bo[where]=sign; addf[k1].push_back(mp(where,1));
idx[where]=addf[k1].size()-1;
} else addf[k1][idx[where]].se+=1;
}
}
}
int gtw=0;
void trylink(int now,int mid,int n,int *A,int *d,int u,int v){
int preA[NL*2],pred[NL*2];
for (int i=0;i<=n;i++) preA[i]=A[i],pred[i]=d[i];
if (now>n||now>mid+K){
normalize(A,n);
atom res=getatom(A,d,n);
if (res.m!=-1){
res.checkvalid();
int where=addin(res);
if (bo[where]!=sign){
bo[where]=sign; gof[u][v].push_back(mp(where,1));
idx[where]=gof[u][v].size()-1;++gtw;
} else {
assert(gof[u][v].size()>idx[where]);
gof[u][v][idx[where]].se+=1;
}
}
for (int i=0;i<=n;++i){
A[i]=preA[i],d[i]=pred[i];
}
return;
}
if (d[now]==2||n-now+1<=K||now<=K) trylink(now+1,mid,n,A,d,u,v);
int l=max(1,now-K);
if (d[now]==1||(d[now]==0&&(n-now+1<=K||now<=K))){
for (int i=l;i<=mid;i++){
if (link(A,d,i,now,n)) trylink(now+1,mid,n,A,d,u,v);
for (int k=0;k<=n;k++) A[k]=preA[k],d[k]=pred[k];
}
}
if (d[now]==0){
for (int i=l;i<=mid;i++)
for (int j=i+1;j<=mid;j++){
if (link(A,d,i,now,n)&&link(A,d,j,now,n)) trylink(now+1,mid,n,A,d,u,v);
for (int k=0;k<=n;k++) A[k]=preA[k],d[k]=pred[k];
}
}
}
void getgo(int k1,int k2){
sign++;
if (x[k2].d[0]==0) return;
int n=x[k1].m+x[k2].m,ma=0;
static int A[NL*2],d[NL*2];
for (int i=0;i<=x[k1].m;++i){
A[i]=x[k1].A[i]; d[i]=x[k1].d[i]; ma=max(ma,A[i]);
}
for (int i=1;i<=x[k2].m;++i){
A[i+x[k1].m]=x[k2].A[i];
if (A[i+x[k1].m]) A[i+x[k1].m]+=ma;
d[i+x[k1].m]=x[k2].d[i];
}
A[n+1]=x[k2].A[0]+ma; d[n+1]=x[k2].d[0];
if (d[n+1]==1){
if (link(A,d,0,n+1,n+1)==0) return;
}
assert(d[n+1]==2);
trylink(x[k1].m+1,x[k1].m,n,A,d,k1,k2);
}
int g[NS],de[N];
void dfs1(int k1){
sz[k1]=1;
for (int i=0;i<go[k1].size();++i){
int j=go[k1][i]; de[j]=de[k1]+1;
dfs1(j); sz[k1]+=sz[j];
}
}
inline void update(int &k1,long long k2){
k1=(k1+k2)%mo;
}
int getansway(int now,int mid,int n,int* A,int *d){
int preA[NL*2],pred[NL*2];
for (int i=0;i<=n;i++) preA[i]=A[i],pred[i]=d[i];
if (now>n){
return 0;
}
for (int i=1;i<=n;i++){
int num=2-d[i];
for (int j=1;j<=n&#j++)
if (abs(i-j)<=K||n-abs(i-j)<=K&&d[j]<2){
if (i<=mid&&j<=mid&&abs(i-j)<=K) continue;
if (i>mid&&j>mid&&abs(i-j)<=K) continue;
num--;
}
if (num) return 0;
}
int b[10],len=0,ans=0,tot=0;
for (int i=1;i<=n;i++)
if ((abs(now-i)<=K||n-abs(now-i)<=K)&&d[i]<2){
if (now<=mid&&i<=mid&&abs(now-i)<=K) continue;
if (now>mid&&i>mid&&abs(now-i)<=K) continue;
if (i<now) b[++len]=i; else tot++;
}
if (d[now]+tot>=2) ans+=getansway(now+1,mid,n,A,d);
if (d[now]+tot+1>=2&&d[now]<=1){
for (int i=1;i<=len;i++){
int tag=link2(A,d,b[i],now,n);
if (tag==2) ans++;
else if (tag==1) ans+=getansway(now+1,mid,n,A,d);
for (int k=0;k<=n;k++) A[k]=preA[k],d[k]=pred[k];
}
}
if (d[now]==0){
for (int i=1;i<=len;i++)
for (int j=i+1;j<=len;j++){
if (link2(A,d,b[i],now,n)){
int tag=link2(A,d,b[j],now,n);
if (tag==2) ans++;
else if (tag) ans+=getansway(now+1,mid,n,A,d);
}
for (int k=0;k<=n;k++) A[k]=preA[k],d[k]=pred[k];
}
}
return ans;
}
int mergeleaf(int k1){
static int A[NL];
static int d[NL];
int m=x[k1].m;
int now=min(K,x[k1].m);
int ma=0; sign++;
for (int i=0;i<=x[k1].m;++i)
if (x[k1].d[i]!=2) ma=max(ma,x[k1].A[i]);
vector<int>b;
if (x[k1].d[0]==0) return 0;
int n=x[k1].m;
memcpy(A,x[k1].A,sizeof A);
memcpy(d,x[k1].d,sizeof d);
A[n+1]=ma+1; d[n+1]=0;
if (x[k1].d[0]==1){
if (link(A,d,0,n+1,n+1)==0) return 0;
}
int ans=getansway(1,x[k1].m,n+1,A,d);
return ans;
}
int mergestate(int k1,int k2){
sign++;
if (x[k2].d[0]==0||x[k1].d[0]!=x[k2].d[0]||(x[k1].totd!=x[k2].totd&&x[k2].m>=K&&x[k1].m>=K)) return 0;
int n=x[k1].m+x[k2].m,ma=0;
static int A[NL*2],d[NL*2];
for (int i=0;i<=x[k1].m;++i){
A[i]=x[k1].A[i]; d[i]=x[k1].d[i]; ma=max(ma,A[i]);
}
for (int i=1;i<=x[k2].m;++i){
A[i+x[k1].m]=x[k2].A[i];
if (A[i+x[k1].m]) A[i+x[k1].m]+=ma;
d[i+x[k1].m]=x[k2].d[i];
}
A[n+1]=x[k2].A[0]+ma; d[n+1]=x[k2].d[0];
if (d[n+1]==1){
if (link2(A,d,0,n+1,n+1)==0) return 0;
}
if (d[0]!=2) return 0;
assert(d[n+1]==2);
int ans=getansway(1,x[k1].m,n,A,d);
return ans;
}
void getansleaf(){
int ans=0;
for (int i=1;i<=len;i++)
if (f[1][i]){
ans=(ans+1ll*f[1][i]*mergeleaf(i))%mo;
}
printf("%d\n",ans);
}
void getans(int k1){
int ans=0;
for (int i=1;i<=len;i++)
if (f[1][i])
for (int j=1;j<=len;j++)
if (f[k1][j]){
ans=(ans+1ll*f[1][i]*f[k1][j]%mo*mergestate(i,j))%mo;
}
printf("%d\n",ans);
}
void treedp(int k1){
f[k1][1]=1;
for (int i=0;i<go[k1].size();++i){
int j=go[k1][i];
if (k1==1&&i==go[k1].size()-1){
if (sz[j]==1){
getansleaf();
} else {
treedp(j);
getans(j);
}
} else if (sz[j]==1){
memcpy(g,f[k1],sizeof g);
memset(f[k1],0x00,sizeof f[k1]);
for (int a=1;a<=len;a++)
if (g[a]){
for (int k=0;k<addf[a].size();++k)
update(f[k1][addf[a][k].fi],1ll*g[a]*addf[a][k].se);
}
} else {
treedp(j);
memcpy(g,f[k1],sizeof g);
memset(f[k1],0x00,sizeof f[k1]);
for (int a=0;a<allP.size();a++){
int loc1=allP[a].first,loc2=allP[a].second;
int now=1ll*g[loc1]*f[j][loc2]%mo;
if (now){
for (int b=0;b<gof[loc1][loc2].size();++b){
update(f[k1][gof[loc1][loc2][b].fi],1ll*now*gof[loc1][loc2][b].se);
}
}
}
}
}
}
int main(){
scanf("%d%d",&n,&K);
len=1; x[1].m=0; x[1].A[0]=1; x[1].d[0]=0; M[x[1].gethash()]=1;
int now=0,pre=0;
while (1){
pre=now; now=len;
for (int i=1;i<=pre;i++)
for (int j=pre+1;j<=now;j++)
getgo(i,j);
for (int i=pre+1;i<=now;i++)
for (int j=1;j<=now;j++)
getgo(i,j);
for (int i=pre+1;i<=now;i++) getaddf(i);
if (len==now) break;
}
int tot=0;
for (int i=1;i<=len;i++)
for (int j=1;j<=len;j++){
if (gof[i][j].size()) allP.push_back(mp(i,j)),tot+=gof[i][j].size();
}
for (int i=2;i<=n;i++){
int k1=(i-2)/3+1;
scanf("%d",&k1);
go[k1].push_back(i);
}
for (int i=1;i<=len;i++) x[i].gettotd();
dfs1(1);
treedp(1);
}
/*#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
map<ll,int>M;
const int N=1100,NS=2400,NL=10,mo=998244353;
struct atom{
int m;
int A[NL],d[NL];
ll h;
int totd;
void gettotd(){
totd=0;
for (int i=0;i<=m;i++) totd+=2-d[i];
}
ll gethash(){
ll k1=0;
for (int i=0;i<=m;++i) k1=1ll*k1*10+A[i];
for (int i=0;i<=m;++i) k1=1ll*k1*3+d[i];
h=k1; return k1;
}
void print(){
printf("%d\n",m);
for (int i=0;i<=m;i++) printf("%d ",A[i]); puts("");
for (int i=0;i<=m;i++) printf("%d ",d[i]); puts("");
}
void checkvalid(){
for (int i=0;i<=m;i++) if (d[i]!=2) assert(A[i]!=0); else assert(A[i]==0);
int t[20];
memset(t,0x00,sizeof t);
for (int i=0;i<=m;i++) t[A[i]]+=2-d[i];
for (int i=0;i<=m;i++) if (A[i]) assert(t[A[i]]==2);
int num=0;
for (int i=0;i<=m;i++) assert(A[i]<=num+1),num=max(num,A[i]);
}
}x[NS];
int len;
int A[NL],d[NL],t[NL];
vector<pair<int,int> >gof[NS][NS],addf[NS],allP;
int idx[NS],bo[NS],sign;
vector<int>go[N];
int n,K,m,f[N][NS],sz[N];
int addin(atom k1){
k1.gethash();
if (M[k1.h]) return M[k1.h];
assert(len+1<NS);
x[++len]=k1; M[k1.h]=len; return len;
}
int link(int *A,int *d,int u,int v,int n){
if (d[u]==2||d[v]==2||A[u]==A[v]) return 0;
d[u]++; d[v]++;
int k1=A[u],k2=A[v];
for (int i=0;i<=n;i++) if (A[i]==k1) A[i]=k2;
if (d[u]==2) A[u]=0;
if (d[v]==2) A[v]=0;
return 1;
}
int link2(int *A,int *d,int u,int v,int n){
if (d[u]==2||d[v]==2) return 0;
if (A[u]!=A[v]) return link(A,d,u,v,n);
for (int i=0;i<=n;i++)
if (d[i]<2&&A[i]!=A[u]) return 0;
d[u]++; d[v]++;
if (d[u]==2) A[u]=0;
if (d[v]==2) A[v]=0;
return 2;
}
int checkfinal(int *A,int *d,int n){
for (int i=0;i<=n;i++) if (A[i]){
assert(d[i]<2); return 0;
}
for (int i=0;i<=n;i++) assert(d[i]==2);
return 1;
}
void normalize(int *A,int n){
static int w[NL*2];
int now=0;
memset(w,0x00,sizeof w);
for (int i=0;i<=n;i++)
if (A[i]){
if (w[A[i]]) A[i]=w[A[i]];
else {
now++; w[A[i]]=now; A[i]=now;
}
}
}
atom getatom(int *A,int *d,int n){
atom res;
if (n>K*2){
for (int i=K+1;i<=n-K;i++)
if (d[i]!=2){
res.m=-1; return res;
}
int now=K;
for (int i=n-K+1;i<=n;i++){
now++; A[now]=A[i]; d[now]=d[i];
}
n=now;
}
res.m=n;
for (int i=0;i<=n;i++) res.A[i]=A[i];
for (int i=0;i<=n;i++) res.d[i]=d[i];
return res;
}
void getaddf(int k1){
static int A[NL];
static int d[NL];
int m=x[k1].m;
int now=min(K,x[k1].m);
int ma=0; sign++;
for (int i=0;i<=x[k1].m;++i)
if (x[k1].d[i]!=2) ma=max(ma,x[k1].A[i]);
for (int isl=0;isl<2;isl++){
if (isl&&x[k1].d[0]==2) continue;
for (int S=0;S<(1<<now);++S){
if (__builtin_popcount(S)>2) continue;
memcpy(A,x[k1].A,sizeof x[k1].A);
memcpy(d,x[k1].d,sizeof x[k1].d);
A[m+1]=ma+1; d[m+1]=0;
if (isl){
if (link(A,d,0,m+1,m+1)==0) continue;
}
int flag=0;
for (int i=1;i<=now;i++){
if ((S&(1<<i-1))==0) continue;
int id=x[k1].m-now+i;
if (link(A,d,id,m+1,m+1)==0){
flag=1; break;
}
}
if (flag) continue;
normalize(A,m+1);
atom res=getatom(A,d,m+1);
if (res.m==-1) continue;
res.checkvalid();
int where=addin(res);
if (bo[where]!=sign){
bo[where]=sign; addf[k1].push_back(mp(where,1));
idx[where]=addf[k1].size()-1;
} else addf[k1][idx[where]].se+=1;
}
}
}
int gtw=0;
void trylink(int now,int mid,int n,int *A,int *d,int u,int v){
int preA[NL*2],pred[NL*2];
for (int i=0;i<=n;i++) preA[i]=A[i],pred[i]=d[i];
if (now>n||now>mid+K){
normalize(A,n);
atom res=getatom(A,d,n);
if (res.m!=-1){
res.checkvalid();
int where=addin(res);
if (bo[where]!=sign){
bo[where]=sign; gof[u][v].push_back(mp(where,1));
idx[where]=gof[u][v].size()-1;++gtw;
} else {
assert(gof[u][v].size()>idx[where]);
gof[u][v][idx[where]].se+=1;
}
}
for (int i=0;i<=n;++i){
A[i]=preA[i],d[i]=pred[i];
}
return;
}
if (d[now]==2||n-now+1<=K||now<=K) trylink(now+1,mid,n,A,d,u,v);
int l=max(1,now-K);
if (d[now]==1||(d[now]==0&&(n-now+1<=K||now<=K))){
for (int i=l;i<=mid;i++){
if (link(A,d,i,now,n)) trylink(now+1,mid,n,A,d,u,v);
for (int k=0;k<=n;k++) A[k]=preA[k],d[k]=pred[k];
}
}
if (d[now]==0){
for (int i=l;i<=mid;i++)
for (int j=i+1;j<=mid;j++){
if (link(A,d,i,now,n)&&link(A,d,j,now,n)) trylink(now+1,mid,n,A,d,u,v);
for (int k=0;k<=n;k++) A[k]=preA[k],d[k]=pred[k];
}
}
}
void getgo(int k1,int k2){
sign++;
if (x[k2].d[0]==0) return;
int n=x[k1].m+x[k2].m,ma=0;
static int A[NL*2],d[NL*2];
for (int i=0;i<=x[k1].m;++i){
A[i]=x[k1].A[i]; d[i]=x[k1].d[i]; ma=max(ma,A[i]);
}
for (int i=1;i<=x[k2].m;++i){
A[i+x[k1].m]=x[k2].A[i];
if (A[i+x[k1].m]) A[i+x[k1].m]+=ma;
d[i+x[k1].m]=x[k2].d[i];
}
A[n+1]=x[k2].A[0]+ma; d[n+1]=x[k2].d[0];
if (d[n+1]==1){
if (link(A,d,0,n+1,n+1)==0) return;
}
assert(d[n+1]==2);
trylink(x[k1].m+1,x[k1].m,n,A,d,k1,k2);
}
int g[NS],de[N];
void dfs1(int k1){
sz[k1]=1;
for (int i=0;i<go[k1].size();++i){
int j=go[k1][i]; de[j]=de[k1]+1;
dfs1(j); sz[k1]+=sz[j];
}
}
inline void update(int &k1,long long k2){
k1=(k1+k2)%mo;
}
int getansway(int now,int mid,int n,int* A,int *d){
int preA[NL*2],pred[NL*2];
for (int i=0;i<=n;i++) preA[i]=A[i],pred[i]=d[i];
if (now>n){
return 0;
}
for (int i=1;i<=n;i++){
int num=2-d[i];
for (int j=1;j<=n&#j++)
if (abs(i-j)<=K||n-abs(i-j)<=K&&d[j]<2){
if (i<=mid&&j<=mid&&abs(i-j)<=K) continue;
if (i>mid&&j>mid&&abs(i-j)<=K) continue;
num--;
}
if (num) return 0;
}
int b[10],len=0,ans=0,tot=0;
for (int i=1;i<=n;i++)
if ((abs(now-i)<=K||n-abs(now-i)<=K)&&d[i]<2){
if (now<=mid&&i<=mid&&abs(now-i)<=K) continue;
if (now>mid&&i>mid&&abs(now-i)<=K) continue;
if (i<now) b[++len]=i; else tot++;
}
if (d[now]+tot>=2) ans+=getansway(now+1,mid,n,A,d);
if (d[now]+tot+1>=2&&d[now]<=1){
for (int i=1;i<=len;i++){
int tag=link2(A,d,b[i],now,n);
if (tag==2) ans++;
else if (tag==1) ans+=getansway(now+1,mid,n,A,d);
for (int k=0;k<=n;k++) A[k]=preA[k],d[k]=pred[k];
}
}
if (d[now]==0){
for (int i=1;i<=len;i++)
for (int j=i+1;j<=len;j++){
if (link2(A,d,b[i],now,n)){
int tag=link2(A,d,b[j],now,n);
if (tag==2) ans++;
else if (tag) ans+=getansway(now+1,mid,n,A,d);
}
for (int k=0;k<=n;k++) A[k]=preA[k],d[k]=pred[k];
}
}
return ans;
}
int mergeleaf(int k1){
static int A[NL];
static int d[NL];
int m=x[k1].m;
int now=min(K,x[k1].m);
int ma=0; sign++;
for (int i=0;i<=x[k1].m;++i)
if (x[k1].d[i]!=2) ma=max(ma,x[k1].A[i]);
vector<int>b;
if (x[k1].d[0]==0) return 0;
int n=x[k1].m;
memcpy(A,x[k1].A,sizeof A);
memcpy(d,x[k1].d,sizeof d);
A[n+1]=ma+1; d[n+1]=0;
if (x[k1].d[0]==1){
if (link(A,d,0,n+1,n+1)==0) return 0;
}
int ans=getansway(1,x[k1].m,n+1,A,d);
return ans;
}
int mergestate(int k1,int k2){
sign++;
if (x[k2].d[0]==0||x[k1].d[0]!=x[k2].d[0]||(x[k1].totd!=x[k2].totd&&x[k2].m>=K&&x[k1].m>=K)) return 0;
int n=x[k1].m+x[k2].m,ma=0;
static int A[NL*2],d[NL*2];
for (int i=0;i<=x[k1].m;++i){
A[i]=x[k1].A[i]; d[i]=x[k1].d[i]; ma=max(ma,A[i]);
}
for (int i=1;i<=x[k2].m;++i){
A[i+x[k1].m]=x[k2].A[i];
if (A[i+x[k1].m]) A[i+x[k1].m]+=ma;
d[i+x[k1].m]=x[k2].d[i];
}
A[n+1]=x[k2].A[0]+ma; d[n+1]=x[k2].d[0];
if (d[n+1]==1){
if (link2(A,d,0,n+1,n+1)==0) return 0;
}
if (d[0]!=2) return 0;
assert(d[n+1]==2);
int ans=getansway(1,x[k1].m,n,A,d);
return ans;
}
void getansleaf(){
int ans=0;
for (int i=1;i<=len;i++)
if (f[1][i]){
ans=(ans+1ll*f[1][i]*mergeleaf(i))%mo;
}
printf("%d\n",ans);
}
void getans(int k1){
int ans=0;
for (int i=1;i<=len;i++)
if (f[1][i])
for (int j=1;j<=len;j++)
if (f[k1][j]){
ans=(ans+1ll*f[1][i]*f[k1][j]%mo*mergestate(i,j))%mo;
}
printf("%d\n",ans);
}
void treedp(int k1){
f[k1][1]=1;
for (int i=0;i<go[k1].size();++i){
int j=go[k1][i];
if (k1==1&&i==go[k1].size()-1){
if (sz[j]==1){
getansleaf();
gof[i][j].size();
}
for (int i=2;i<=n;i++){
int k1=(i-2)/3+1;
scanf("%d",&k1);
go[k1].push_back(i);
}
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()
template <typename T>
inline bool chkmin(T &a, const T &b) {
return b < a ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, const T &b) {
return a < b ? a = b, 1 : 0;
}
typedef long long LL;
const int oo = 0x3f3f3f3f;
const int __buffsize = 100000;
char __buff[__buffsize];
char *__buffs, *__buffe;
#define getc() \
(__buffs == __buffe ? fread(__buff, 1, __buffsize, stdin), __buffe = __buff + __buffsize, \
*((__buffs = __buff)++) : *(__buffs++))
template <typename T>
inline T &Read(T &x) {
static char c;
while (1) {
c = getc();
if (c == '-' || (c >= '0' && c <= '9'))
break;
}
bool flag = c == '-';
x = flag ? 0 : c - '0';
while (1) {
c = getc();
if (c < '0' || c > '9')
break;
(x *= 10) += c - '0';
}
if (flag)
x = -x;
return x;
}
#undef getc
const int maxn = 500010, maxm = 1000100;
struct edge {
int id, g, nxt;
edge() {}
edge(int _id, int _g, int _nxt) : id(_id), g(_g), nxt(_nxt) {}
};
int en;
int st[maxn + 5];
edge e[(maxm << 1) + 5];
inline void add_edge(int x, int y, int z) { e[en] = edge(y, z, st[x]), st[x] = en++; }
int n, m;
int S, T;
bool bad[maxn + 5];
int buffer[maxn + 5];
int dfn_cnt = 0;
int dfn[maxn + 5], low[maxn + 5];
bool has_T[maxn + 5];
void get_bad_vertices(int x) {
if (x == T)
has_T[x] = 1;
dfn[x] = low[x] = dfn_cnt++;
int cnt = 0;
for (int i = st[x]; ~i; i = e[i].nxt) {
int y = e[i].id;
if (!~dfn[y]) {
get_bad_vertices(y);
if (has_T[y])
has_T[x] = 1;
if (has_T[y] || low[y] < dfn[x]) {
cnt += buffer[x];
chkmin(low[x], low[y]);
}
buffer[x] = 0;
} else if (dfn[y] < dfn[x]) {
++cnt;
++buffer[y];
chkmin(low[x], dfn[y]);
}
}
if (cnt <= 2 && x != S && x != T) {
bad[x] = 1;
}
}
LL dis[maxn + 5];
bool on_path[maxm + 5];
int pathn;
int path[maxn + 5];
int id[maxn + 5];
inline void get_path() {
static bool vis[maxn + 5];
static int pre[maxn + 5];
priority_queue<pair<LL, int>, vector<pair<LL, int> >, greater<pair<LL, int> > > q;
memset(dis, oo, sizeof(dis[0]) * n);
memset(vis, 0, sizeof(vis[0]) * n);
q.push(mp(0, S));
dis[S] = 0;
while (!q.empty()) {
int x = q.top().y;
q.pop();
if (vis[x])
continue;
vis[x] = 1;
for (int i = st[x]; ~i; i = e[i].nxt) {
int y = e[i].id;
if (!bad[y] && chkmin(dis[y], dis[x] + e[i].g)) {
pre[y] = i ^ 1;
q.push(mp(dis[y], y));
}
}
}
memset(on_path, 0, sizeof(on_path[0]) * m);
pathn = 0;
int cur = T;
while (cur != S) {
path[pathn++] = cur;
on_path[pre[cur] >> 1] = 1;
cur = e[pre[cur]].id;
}
path[pathn++] = cur;
reverse(path, path + pathn);
memset(id, -1, sizeof(id[0]) * n);
REP(i, 0, pathn) id[path[i]] = i;
}
int fa[maxn + 5];
int get(int x) { return fa[x] == x ? x : fa[x] = get(fa[x]); }
int lim[maxn + 5];
inline bool get_lim() {
static bool leftmost[maxn + 5], rightmost[maxn + 5];
static bool vis[maxn + 5];
memset(leftmost, 0, sizeof(leftmost[0]) * pathn);
memset(rightmost, 0, sizeof(rightmost[0]) * pathn);
memset(vis, 0, sizeof(vis[0]) * n);
REP(i, 0, pathn) {
if (!vis[get(path[i])]) {
leftmost[i] = 1;
vis[get(path[i])] = 1;
}
}
memset(vis, 0, sizeof(vis[0]) * n);
for (int i = pathn - 1; i >= 0; --i) {
if (!vis[get(path[i])]) {
rightmost[i] = 1;
vis[get(path[i])] = 1;
}
}
if (leftmost[pathn - 1] || rightmost[0])
return 0;
REP(i, 0, pathn + 1) lim[i] = pathn;
int lst = -1;
REP(i, 0, pathn) {
if (leftmost[i])
lst = i;
if (rightmost[i]) {
if (lst > 0 && i + 1 < pathn) {
lim[lst - 1] = i + 1;
}
}
}
for (int i = pathn - 1; i >= 0; --i) {
chkmin(lim[i], lim[i + 1]);
}
return 1;
}
inline LL work() {
static int vis[maxn + 5];
static int info[maxn + 5];
priority_queue<pair<LL, pair<int, int> >, vector<pair<LL, pair<int, int> > >,
greater<pair<LL, pair<int, int> > > >
q;
memset(vis, 0, sizeof(vis[0]) * n);
q.push(mp(0, mp(S, 0)));
while (!q.empty()) {
LL d = q.top().x;
int x = q.top().y.x, lst = q.top().y.y;
q.pop();
if (x == T) {
return d;
}
if (!vis[x]) {
info[x] = lst;
} else if (vis[x] == 1) {
if (~id[x]) {
if (lim[lst] <= lim[info[x]])
continue;
} else {
if (lst >= info[x])
continue;
}
} else if (vis[x] > 1)
continue;
++vis[x];
for (int i = st[x]; ~i; i = e[i].nxt) {
int y = e[i].id;
if (bad[y])
continue;
if (~id[y]) {
if (id[y] == lst)
continue;
if (!on_path[i >> 1]) {
q.push(mp(d + e[i].g, mp(y, id[y])));
} else if (id[y] < lim[lst]) {
q.push(mp(d + e[i].g, mp(y, lst)));
}
} else {
if (~id[x])
q.push(mp(d + e[i].g, mp(y, id[x])));
else
q.push(mp(d + e[i].g, mp(y, lst)));
}
}
}
return -1;
}
int main() {
Read(n), Read(m);
memset(st, -1, sizeof(st[0]) * n), en = 0;
REP(i, 0, m) {
int x, y, z;
Read(x), Read(y), Read(z), --x, --y;
add_edge(x, y, z);
add_edge(y, x, z);
}
Read(S), Read(T), --S, --T;
memset(buffer, 0, sizeof(buffer[0]) * n);
memset(dfn, -1, sizeof(dfn[0]) * n);
memset(bad, 0, sizeof(bad[0]) * n);
memset(has_T, 0, sizeof(has_T[0]) * n);
dfn_cnt = 0;
get_bad_vertices(S);
get_path();
REP(i, 0, n) fa[i] = i;
REP(i, 0, n)
for (int j = st[i]; ~j; j = e[j].nxt)
if (!on_path[j >> 1])
fa[get(i)] = get(e[j].id);
bool not_connected = 0;
REP(i, 0, n) if (get(i) != get(0)) {
not_connected = 1;
break;
}
if (not_connected) {
if (!get_lim())
printf("-1\n");
else
printf("%lld\n", work());
} else
printf("%lld\n", dis[T]);
return 0;
}#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()
template <typename T>
inline bool chkmin(T &a, const T &b) {
return b < a ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, const T &b) {
return a < b ? a = b, 1 : 0;
}
typedef long long LL;
const int oo = 0x3f3f3f3f;
const int __buffsize = 100000;
char __buff[__buffsize];
char *__buffs, *__buffe;
#define getc() \
(__buffs == __buffe ? fread(__buff, 1, __buffsize, stdin), __buffe = __buff + __buffsize, \
*((__buffs = __buff)++) : *(__buffs++))
template <typename T>
inline T &Read(T &x) {
static char c;
while (1) {
c = getc();
if (c == '-' || (c >= '0' && c <= '9'))
break;
}
bool flag = c == '-';
x = flag ? 0 : c - '0';
while (1) {
c = getc();
if (c < '0' || c > '9')
break;
(x *= 10) += c - '0';
}
if (flag)
x = -x;
return x;
}
#undef getc
const int maxn = 500010, maxm = 1000100;
struct edge {
int id, g, nxt;
edge() {}
edge(int _id, int _g, int _nxt) : id(_id), g(_g), nxt(_nxt) {}
};
int en;
int st[maxn + 5];
edge e[(maxm << 1) + 5];
inline void add_edge(int x, int y, int z) { e[en] = edge(y, z, st[x]), st[x] = en++; }
int n, m;
int S, T;
bool bad[maxn + 5];
int buffer[maxn + 5];
int dfn_cnt = 0;
int dfn[maxn + 5], low[maxn + 5];
bool has_T[maxn + 5];
void get_bad_vertices(int x) {
if (x == T)
has_T[x] = 1;
dfn[x] = low[x] = dfn_cnt++;
int cnt = 0;
for (int i = st[x]; ~i; i = e[i].nxt) {
int y = e[i].id;
if (!~dfn[y]) {
get_bad_vertices(y);
if (has_T[y])
has_T[x] = 1;
if (has_T[y] || low[y] < dfn[x]) {
cnt += buffer[x];
chkmin(low[x], low[y]);
}
buffer[x] = 0;
} else if (dfn[y] < dfn[x]) {
++cnt;
++buffer[y];
chkmin(low[x], dfn[y]);
}
}
if (cnt <= 2 && x != S && x != T) {
bad[x] = 1;
}
}
LL dis[maxn + 5];
bool on_path[maxm + 5];
int pathn;
int path[maxn + 5];
int id[maxn + 5];
inline void get_path() {
static bool vis[maxn + 5];
static int pre[maxn + 5];
priority_queue<pair<LL, int>, vector<pair<LL, int> >, greater<pair<LL, int> > > q;
memset(dis, oo, sizeof(dis[0]) * n);
memset(vis, 0, sizeof(vis[0]) * n);
q.push(mp(0, S));
dis[S] = 0;
while (!q.empty()) {
int x = q.top().y;
q.pop();
if (vis[x])
continue;
vis[x] = 1;
for (int i = st[x]; ~i; i = e[i].nxt) {
int y = e[i].id;
if (!bad[y] && chkmin(dis[y], dis[x] + e[i].g)) {
pre[y] = i ^ 1;
q.push(mp(dis[y], y));
}
}
}
memset(on_path, 0, sizeof(on_path[0]) * m);
pathn = 0;
int cur = T;
while (cur != S) {
path[pathn++] = cur;
on_path[pre[cur] >> 1] = 1;
cur = e[pre[cur]].id;
}
path[pathn++] = cur;
reverse(path, path + pathn);
memset(id, -1, sizeof(id[0]) * n);
REP(i, 0, pathn) id[path[i]] = i;
}
int fa[maxn + 5];
int get(int x) { return fa[x] == x ? x : fa[x] = get(fa[x]); }
int lim[maxn + 5];
inline bool get_lim() {
static bool leftmost[maxn + 5], rightmost[maxn + 5];
static bool vis[maxn + 5];
memset(leftmost, 0, sizeof(leftmost[0]) * pathn);
memset(rightmost, 0, sizeof(rightmost[0]) * pathn);
memset(vis, 0, sizeof(vis[0]) * n);
REP(i, 0, pathn) {
if (!vis[get(path[i])]) {
leftmost[i] = 1;
vis[get(path[i])] = 1;
}
}
memset(vis, 0, sizeof(vis[0]) * n);
for (int i = pathn - 1; i >= 0; --i) {
if (!vis[get(path[i])]) {
rightmost[i] = 1;
vis[get(path[i])] = 1;
}
}
if (leftmost[pathn - 1] || rightmost[0])
return 0;
REP(i, 0, pathn + 1) lim[i] = pathn;
int lst = -1;
REP(i, 0, pathn) {
if (leftmost[i])
lst = i;
if (rightmost[i]) {
if (lst > 0 && i + 1 < pathn) {
lim[lst - 1] = i + 1;
}
}
}
for (int i = pathn - 1; i >= 0; --i) {
chkmin(lim[i], lim[i + 1]);
}
return 1;
}
inline LL work() {
static int vis[maxn + 5];
static int info[maxn + 5];
priority_queue<pair<LL, pair<int, int> >, vector<pair<LL, pair<int, int> > >,
greater<pair<LL, pair<int, int> > > >
q;
memset(vis, 0, sizeof(vis[0]) * n);
q.push(mp(0, mp(S, 0)));
while (!q.empty()) {
LL d = q.top().x;
int x = q.top().y.x, lst = q.top().y.y;
q.pop();
if (x == T) {
return d;
}
if (!vis[x]) {
info[x] = lst;
} else if (vis[x] == 1) {
if (~id[x]) {
if (lim[lst] <= lim[info[x]])
continue;
} else {
if (lst >= info[x])
continue;
}
} else if (vis[x] > 1)
continue;
++vis[x];
for (int i = st[x]; ~i; i = e[i].nxt) {
int y = e[i].id;
if (bad[y])
continue;
if (~id[y]) {
if (id[y] == lst)
continue;
if (!on_path[i >> 1]) {
q.push(mp(d + e[i].g, mp(y, id[y])));
} else if (id[y] < lim[lst]) {
q.push(mp(d + e[i].g, mp(y, lst)));
}
} else {
if (~id[x])
q.push(mp(d + e[i].g, mp(y, id[x])));
else
q.push(mp(d + e[i].g, mp(y, lst)));
}
}
}
return -1;
}
int main() {
Read(n), Read(m);
memset(st, -1, sizeof(st[0]) * n), en = 0;
REP(i, 0, m) {
int x, y, z;
Read(x), Read(y), Read(z), --x, --y;
add_edge(x, y, z);
add_edge(y, x, z);
}
Read(S), Read(T), --S, --T;
memset(buffer, 0, sizeof(buffer[0]) * n);
memset(dfn, -1, sizeof(dfn[0]) * n);
memset(bad, 0, sizeof(bad[0]) * n);
memset(has_T, 0, sizeof(has_T[0]) * n);
dfn_cnt = 0;
get_bad_vertices(S);
get_path();
REP(i, 0, n) fa[i] = i;
REP(i, 0, n)
for (int j = st[i]; ~j; j = e[j].nxt)
if (!on_path[j >> 1])
fa[get(i)] = get(e[j].id);
bool not_connected = 0;
REP(i, 0, n) if (get(i) != get(0)) {
not_connected = 1;
break;
}
if (not_connected) {
if (!get_lim())
printf("-1\n");
else
printf("%lld\n", work());
} else
printf("%lld\n", dis[T]);
return 0;
}
for (int i=1;i<=len;i++) x[i].gettotd();
dfs1(1);
treedp(1);
}*/
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 5
Accepted
time: 857ms
memory: 119892kb
input:
5 3 1 1 1 3
output:
2
result:
ok single line: '2'
Test #2:
score: 5
Accepted
time: 878ms
memory: 120348kb
input:
10 3 1 2 3 4 5 2 5 4 1
output:
16
result:
ok single line: '16'
Test #3:
score: 5
Accepted
time: 888ms
memory: 120312kb
input:
15 3 1 1 2 1 1 1 3 3 1 1 1 1 1 1
output:
23854
result:
ok single line: '23854'
Test #4:
score: 5
Accepted
time: 864ms
memory: 119064kb
input:
20 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 18 18
output:
24097065
result:
ok single line: '24097065'
Test #5:
score: 5
Accepted
time: 4ms
memory: 14312kb
input:
1000 1 1 2 3 4 5 6 7 8 7 10 11 10 6 14 15 16 17 18 19 19 21 18 23 23 17 26 27 26 29 30 30 32 29 16 35 36 35 15 39 39 41 41 43 43 14 46 46 48 49 48 5 52 53 54 53 56 56 58 58 52 61 62 63 63 65 66 67 66 69 69 71 71 65 74 62 76 76 78 79 79 81 78 83 83 85 85 87 61 89 90 89 92 92 4 95 96 97 98 98 97 96 10...
output:
0
result:
ok single line: '0'
Test #6:
score: 5
Accepted
time: 7ms
memory: 14364kb
input:
999 1 1 2 3 4 5 6 7 8 9 10 10 9 13 13 8 7 17 18 19 20 21 22 22 21 20 26 26 19 29 30 30 32 32 29 35 35 37 38 38 37 18 42 43 43 42 46 46 17 49 50 50 49 53 54 54 53 6 58 59 60 61 62 63 63 65 65 62 61 60 70 70 72 72 59 75 76 77 77 76 75 81 81 58 84 85 86 86 88 89 90 90 92 92 89 88 96 97 97 96 100 100 85...
output:
2
result:
ok single line: '2'
Test #7:
score: 5
Accepted
time: 4ms
memory: 13156kb
input:
1000 1 1 2 3 4 5 6 7 8 9 10 11 12 13 13 12 16 17 17 19 19 21 21 16 24 24 11 10 28 29 29 28 32 33 34 34 33 37 37 32 40 40 9 43 43 8 46 46 7 49 50 50 49 53 53 55 55 6 58 59 60 61 61 63 63 60 59 67 68 69 69 68 67 73 74 74 76 76 78 78 73 58 82 83 83 85 85 82 88 89 89 88 92 92 94 94 96 96 5 99 100 100 10...
output:
1
result:
ok single line: '1'
Test #8:
score: 5
Accepted
time: 3ms
memory: 9580kb
input:
1000 1 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 11 11 11 12 12 12 13 13 13 14 14 14 15 15 15 16 16 16 17 17 17 18 18 18 19 19 19 20 20 20 21 21 21 22 22 22 23 23 23 24 24 24 25 25 25 26 26 26 27 27 27 28 28 28 29 29 29 30 30 30 31 31 31 32 32 32 33 33 33 34 34 34 35 35 35 36 36...
output:
106890205
result:
ok single line: '106890205'
Test #9:
score: 5
Accepted
time: 7ms
memory: 8956kb
input:
1000 1 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 1 3 2 4 6 3 1 2 3 7 1 6 7 1 4 2 2 6 4 7 7 1 48 48 48 49 49 49 50 50 50 51 51 51 52 52 52 53 53 53 54 54 54 55 55 55 56 56 56 57 57 57 58 58 58 59 59 59 60 60 60 61 61 61 62 62 62 63 63 63 64 64 64 65 65 65 66 66 66 67 67 67 68 68 68 69 69 69 7...
output:
420850835
result:
ok single line: '420850835'
Test #10:
score: 5
Accepted
time: 7ms
memory: 12048kb
input:
1000 1 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 11 11 11 12 12 12 13 13 13 14 14 14 15 15 15 16 16 16 17 17 17 18 18 18 19 19 19 20 20 20 21 21 21 22 22 22 23 23 23 24 24 24 25 25 25 26 26 26 27 27 27 28 28 28 29 29 29 30 30 30 31 31 31 32 32 32 33 33 33 34 34 34 35 35 35 36 36...
output:
570335790
result:
ok single line: '570335790'
Test #11:
score: 5
Accepted
time: 10ms
memory: 14996kb
input:
1000 2 1 2 3 4 5 6 7 8 8 7 6 12 12 5 15 4 17 18 19 20 21 22 23 22 25 26 26 28 28 30 30 25 21 34 35 36 36 35 39 39 41 41 34 44 45 45 47 44 20 50 51 52 53 52 51 56 57 57 56 50 61 62 63 64 65 65 67 67 69 64 71 72 73 74 75 75 74 73 72 80 80 82 63 84 84 86 86 62 89 90 90 89 93 94 95 95 97 94 99 99 93 102...
output:
178991712
result:
ok single line: '178991712'
Test #12:
score: 5
Accepted
time: 13ms
memory: 15092kb
input:
1000 2 1 2 3 4 5 6 7 8 9 9 11 8 13 13 7 16 17 16 19 19 21 6 5 24 25 25 27 24 29 29 31 4 33 34 35 36 36 35 39 34 41 42 42 41 33 46 47 48 48 47 46 3 53 54 55 56 55 58 58 54 53 62 63 62 65 65 67 2 69 70 71 72 72 74 71 76 77 77 79 79 76 70 83 84 85 86 87 88 89 90 90 92 93 94 93 92 89 98 99 99 98 102 103...
output:
460227781
result:
ok single line: '460227781'
Test #13:
score: 5
Accepted
time: 13ms
memory: 15040kb
input:
1000 2 1 2 3 4 5 6 7 8 7 6 11 5 13 13 15 15 17 17 4 20 20 22 23 24 25 26 26 25 24 30 23 32 22 34 35 36 37 38 38 37 36 42 43 44 44 46 43 48 48 50 50 42 53 54 55 55 57 58 58 57 61 61 54 53 65 65 67 67 35 70 71 70 34 74 75 76 77 78 78 77 81 82 82 84 84 81 76 88 89 88 91 92 93 93 92 91 97 98 97 100 100 ...
output:
125424813
result:
ok single line: '125424813'
Test #14:
score: 5
Accepted
time: 11ms
memory: 8848kb
input:
1000 2 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 11 11 11 12 12 12 13 13 13 14 14 14 15 15 15 16 16 16 17 17 17 18 18 18 19 19 19 20 20 20 21 21 21 22 22 22 23 23 23 24 24 24 25 25 25 26 26 26 27 27 27 28 28 28 29 29 29 30 30 30 31 31 31 32 32 32 33 33 33 34 34 34 35 35 35 36 36...
output:
23756983
result:
ok single line: '23756983'
Test #15:
score: 5
Accepted
time: 11ms
memory: 9520kb
input:
1000 2 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 11 11 11 12 12 12 13 13 13 14 14 14 15 15 15 16 16 16 17 17 17 18 18 18 19 19 19 20 20 20 21 21 21 22 22 3 4 19 11 19 15 10 1 3 21 10 9 17 20 5 12 16 7 12 12 11 2 4 7 4 20 3 21 2 4 16 2 11 16 16 8 4 15 14 12 1 6 7 11 19 8 1 6 2 2 ...
output:
325532742
result:
ok single line: '325532742'
Test #16:
score: 5
Accepted
time: 11ms
memory: 9184kb
input:
1000 2 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 11 11 11 12 12 12 13 13 13 14 14 14 15 15 15 16 16 16 17 17 17 18 18 18 19 19 19 20 20 20 21 21 21 22 22 22 23 23 23 24 24 24 25 25 25 26 26 26 27 27 27 28 28 28 29 29 29 30 30 30 31 31 31 32 32 32 33 33 33 34 34 34 35 35 35 36 36...
output:
116800683
result:
ok single line: '116800683'
Test #17:
score: 5
Accepted
time: 1346ms
memory: 125576kb
input:
1000 3 1 2 3 4 5 6 5 8 9 10 11 12 12 11 15 10 17 18 17 20 21 22 21 20 9 26 27 28 28 27 26 32 32 34 8 36 36 38 39 40 40 39 43 43 45 38 47 48 48 47 4 52 52 54 54 3 57 58 59 60 61 61 60 64 59 66 67 67 69 66 71 72 73 72 71 76 77 77 76 58 81 82 83 83 82 86 87 88 89 88 91 92 92 91 95 95 87 98 86 100 100 1...
output:
767516039
result:
ok single line: '767516039'
Test #18:
score: 5
Accepted
time: 1302ms
memory: 125308kb
input:
1000 3 1 2 3 4 5 6 7 7 6 10 11 12 10 5 15 15 4 18 19 20 21 22 22 21 25 26 26 25 29 20 31 32 32 34 34 31 37 19 39 39 18 42 43 44 45 46 45 48 48 50 44 52 52 54 43 56 57 58 59 59 61 62 62 61 58 66 67 67 66 57 71 72 72 71 56 76 77 78 77 76 81 81 42 84 85 86 86 85 89 90 89 92 93 92 84 96 3 98 99 100 101 ...
output:
776061489
result:
ok single line: '776061489'
Test #19:
score: 5
Accepted
time: 1251ms
memory: 121884kb
input:
1000 3 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 11 11 11 12 12 12 13 13 13 14 14 14 15 15 15 16 16 16 17 17 17 18 18 18 19 19 19 20 20 20 21 21 21 22 22 22 23 23 23 24 24 24 25 25 25 26 26 26 27 27 27 28 28 28 29 29 29 30 30 30 31 31 31 32 32 32 33 33 33 34 34 34 35 35 35 36 36...
output:
357633930
result:
ok single line: '357633930'
Test #20:
score: 5
Accepted
time: 1256ms
memory: 120808kb
input:
1000 3 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 11 11 11 12 12 12 13 13 13 14 14 14 15 15 15 16 16 16 17 17 17 18 18 18 19 19 19 20 20 20 21 21 21 22 22 22 23 23 23 24 24 24 25 25 25 26 26 26 27 27 27 28 28 28 29 29 29 30 30 30 31 31 31 32 32 32 33 33 33 34 34 34 35 35 35 36 36...
output:
568729964
result:
ok single line: '568729964'
Extra Test:
score: 0
Extra Test Passed