QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#664163 | #9491. 生命的循环 | 275307894a | 100 ✓ | 725ms | 37548kb | C++14 | 4.7kb | 2024-10-21 19:26:06 | 2024-10-21 19:26:08 |
Judging History
answer
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=5000+5,M=N*120+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(263082);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
#ifdef LOCAL
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
#else
#define gdb(...) void()
#endif
}using namespace Debug;
int n,m,type,k;
int X[N*2],Y[N*2],Z[N*2];
vector<int> S[N];
int scc[N];
namespace Tarjan{
int dfn[N],low[N],dh,st[N],sh;
void tarjan(int x){
dfn[x]=low[x]=++dh;st[++sh]=x;
for(int i:S[x]){
if(!dfn[i]) tarjan(i),low[x]=min(low[x],low[i]);
else if(!scc[i]) low[x]=min(low[x],dfn[i]);
}
if(low[x]==dfn[x]){
++k;
while(st[sh+1]^x) scc[st[sh]]=k,sh--;
}
}
void build(){
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
}
}
vector<int> V[N],G1[N],G2[N];
bitset<101> g1[N][101],g2[N][101];
int w[N];
int qryGCD(int x){
static int dis[N];
for(int i=101;i;i--){
for(int j:V[x]) dis[j]=-1;
dis[V[x][0]]=0;
queue<int> q;
q.push(V[x][0]);
int flag=0;
while(!q.empty()){
int x=q.front();q.pop();
for(int j:G1[x]){
int y=Y[j];
if(~dis[y]){
if(dis[y]!=(dis[x]+Z[j])%i) {flag=1;break;}
}else dis[y]=(dis[x]+Z[j])%i,q.push(y);
}
}
if(!flag) return i;
}
return 0;
}
void dfs1(int x,int a,int b){
if(g1[x][a][b]) return;
g1[x][a][b]=1;
for(int i:G2[x]) dfs1(Y[i],a,(b+Z[i])%a);
}
void dfs2(int x,int a,int b){
if(w[scc[x]]^101) a=__gcd(a,w[scc[x]]),b%=a;
if(g2[x][a][b]) return;
g2[x][a][b]=1;
for(int i:G2[x]) dfs2(Y[i],a,(b+Z[i])%a);
}
namespace BigInt{
int k,ans[N];
void init(){
k=0;ans[0]=1;
}
void mul(int x){
int w=0;
for(int i=k;~i;i--) w=(w*10+ans[i])%x;
x/=__gcd(w,x);
for(int i=0;i<=k;i++) ans[i]*=x;
for(int i=0;i<k;i++) ans[i+1]+=ans[i]/10,ans[i]%=10;
while(ans[k]>=10) ans[k+1]=ans[k]/10,ans[k]%=10,k++;
}
void print(){
ll w=0;
const int mod=1e9+9;
for(int i=k;~i;i--) w=(w*10+ans[i])%mod;
printf("%lld\n",w);
}
}
bitset<105> g[105],vis[105],f[105],msk;
const int I=32*27*5*7;
int G[N];
void Solve(){
scanf("%d%d%d",&n,&m,&type);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&X[i],&Y[i],&Z[i]);
S[X[i]].push_back(Y[i]);
}
Tarjan::build();
for(int i=1;i<=m;i++){
if(scc[X[i]]==scc[Y[i]]) G1[X[i]].push_back(i);
G2[X[i]].push_back(i);
}
for(int i=1;i<=n;i++) V[scc[i]].push_back(i);
for(int i=1;i<=k;i++) w[i]=qryGCD(i);
for(int i=1;i<=100;i++) dfs1(1,i,0);
for(int i=1;i<=n;i++) if(w[scc[i]]^101){
for(int y=0;y<w[scc[i]];y++) if(g1[i][w[scc[i]]][y]) dfs2(i,w[scc[i]],y);
}
BigInt::init();
for(int x=1;x<=100;x++) for(int y=0;y<x;y++) g[x][y]=g2[n][x][y];
for(int x=1;x<=100;x++) G[x]=__gcd(I,x);
for(int i=0;i<I;i++){
int flag=0;
for(int x=1;x<=100;x++) f[x].set();
for(int x=1;x<=100;x++){
int w=G[x];
if(x==w){
if(g[x][i%w]){flag=1;break;}
continue;
}
msk.reset();
for(int y=i%w;y<x;y+=w)if(!g[x][y]) msk.set(y%(x/w));
f[x/w]&=msk;
}
for(int x=1;x<=100;x++) if(!f[x].count()) flag=1;
if(flag) continue;
for(int x=1;x<=100;x++){
int w=G[x];
if(x==w){
vis[x].set(i%w);
continue;
}
for(int y=i%w;y<x;y+=w) if(f[x/w][y%(x/w)]) vis[x].set(y);
}
}
for(int x=1;x<=100;x++){
for(int y=0;y<x;y++) if(!vis[x][y]) g[x][y]=1;
vis[x].reset();
}
for(int x=1;x<=100;x++){
for(int y=0;y<x;y++) if(g[x][y]){
for(int z=2;x*z<=100;z++){
for(int b=y;b<x*z;b+=x) g[x*z][b]=1,vis[x*z][b]=1;
}
}
}
for(int x=100;x;x--){
for(int y=0;y<x;y++)if(!g[x][y]){
for(int z=2;x*z<=100;z++){
int flag=0;
for(int b=y;b<x*z;b+=x) if(!g[x*z][b]) flag=1;
if(!flag){
g[x][y]=1;
for(int b=y;b<x*z;b+=x) vis[x*z][b]=1;
}
}
}
}
for(int x=100;x;x--){
for(int y=0;y<x;y++) if(!vis[x][y]&&g[x][y]){gdb(x);BigInt::mul(x);break;}
}
// for(int i=1;;i++) if(604422963ll*i%mod==208845917) gdb(i);
BigInt::print();
}
int main(){
int t=1;
// scanf("%d",&t);
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 275ms
memory: 6520kb
input:
30 2000 1 9 19 58 20 17 5 20 17 96 27 20 2 15 28 71 14 18 20 19 24 29 18 13 66 21 17 62 20 17 86 23 20 58 18 26 69 29 18 73 30 26 13 27 17 73 23 15 30 10 8 68 25 6 51 7 4 55 23 13 74 12 8 94 23 29 33 6 8 86 1 8 75 14 30 73 23 27 82 14 26 85 12 28 68 1 27 21 6 8 74 22 13 61 17 5 58 28 3 69 1 25 59 11...
output:
1
result:
ok single line: '1'
Test #2:
score: 1
Accepted
time: 254ms
memory: 5068kb
input:
3000 10000 1 2941 1762 34 1456 1466 41 1279 2756 45 396 2841 46 579 12 78 2654 888 18 1656 237 58 1820 2775 80 426 165 3 994 1141 92 1617 1851 28 2449 2082 75 1438 2206 34 2657 774 78 942 1156 40 2329 176 92 858 2172 84 1161 2798 72 982 435 43 1674 1274 88 2827 979 9 1003 1165 50 907 774 81 1142 204...
output:
1
result:
ok single line: '1'
Subtask #2:
score: 8
Accepted
Test #3:
score: 8
Accepted
time: 136ms
memory: 4544kb
input:
5 8 2 1 5 0 4 1 0 5 4 0 3 2 2 2 2 2 4 5 2 4 3 0 1 1 0
output:
2
result:
ok single line: '2'
Test #4:
score: 8
Accepted
time: 168ms
memory: 6008kb
input:
7 11 2 1 2 1 2 3 3 3 2 5 2 7 1 3 7 2 1 5 3 5 5 6 5 7 1 1 6 2 6 6 10 6 7 4
output:
60
result:
ok single line: '60'
Test #5:
score: 8
Accepted
time: 141ms
memory: 6000kb
input:
7 15 2 1 2 1 2 2 8 2 7 10 1 3 8 3 3 3 3 7 2 1 4 8 4 4 10 4 7 6 1 5 3 5 5 9 5 7 4 1 6 4 6 6 6 6 7 0
output:
120
result:
ok single line: '120'
Subtask #3:
score: 11
Accepted
Test #6:
score: 11
Accepted
time: 447ms
memory: 23240kb
input:
5000 5259 3 1 8 5 8 7 1 7 9 5 9 4 2 4 5 4 5 3 1 3 2 2 2 6 1 6 10 3 10 1 4 5 11 46 11 5 38 2 14 14 14 13 22 13 15 12 15 12 14 12 16 21 16 2 15 7 26 0 26 28 2 28 25 1 25 23 2 23 20 4 20 24 1 24 22 1 22 21 1 21 27 3 27 30 0 30 19 4 19 18 3 18 17 3 17 29 2 29 7 1 14 33 12 33 31 13 31 36 11 36 34 5 34 38...
output:
14
result:
ok single line: '14'
Test #7:
score: 11
Accepted
time: 311ms
memory: 12904kb
input:
2000 2189 3 1 2 0 2 1 0 2 3 0 3 4 0 4 2 0 2 5 0 5 2 0 3 6 25 6 3 23 2 18 4 18 16 0 16 8 5 8 9 3 9 19 8 19 12 5 12 23 1 23 24 6 24 10 5 10 15 6 15 17 6 17 21 9 21 22 4 22 7 6 7 25 5 25 11 4 11 20 5 20 13 5 13 14 6 14 2 3 17 26 0 26 17 0 26 28 0 28 27 0 27 26 0 3 93 0 93 70 1 70 158 0 158 95 1 95 189 ...
output:
48
result:
ok single line: '48'
Test #8:
score: 11
Accepted
time: 283ms
memory: 5540kb
input:
100 7000 3 11 14 0 41 73 0 58 2 0 85 30 0 69 59 0 3 84 0 55 87 0 50 66 0 37 89 0 25 100 0 100 63 0 73 30 0 79 83 0 3 84 0 25 28 0 51 57 0 79 47 0 55 19 0 60 68 0 42 53 0 36 47 0 76 32 0 60 78 0 65 71 0 73 15 0 7 61 0 31 19 0 92 32 0 74 21 0 7 43 0 21 56 0 66 5 0 34 88 0 95 5 0 25 55 0 54 88 0 44 97 ...
output:
3
result:
ok single line: '3'
Subtask #4:
score: 10
Accepted
Dependency #3:
100%
Accepted
Test #9:
score: 10
Accepted
time: 411ms
memory: 24320kb
input:
5000 5287 4 1 2 41 1 20 1 20 21 2 21 38 1 38 32 1 32 40 0 40 8 3 8 35 2 35 15 0 15 19 2 19 31 2 31 12 1 12 50 4 50 36 3 36 5 1 5 22 1 22 43 2 43 26 0 26 25 3 25 23 0 23 17 3 17 42 1 42 13 4 13 9 3 9 37 1 37 52 2 52 4 1 4 49 1 49 48 3 48 24 1 24 6 0 6 55 2 55 30 0 30 18 0 18 11 1 11 14 0 14 51 2 51 1...
output:
30
result:
ok single line: '30'
Test #10:
score: 10
Accepted
time: 504ms
memory: 13616kb
input:
5000 10000 4 4998 4999 12 4999 5000 18 5000 4998 42 1 2 17 2 3 43 3 4 12 4 5 32 5 6 10 6 7 45 7 8 22 8 9 17 9 10 45 10 11 33 11 12 1 12 13 10 13 14 2 14 15 43 15 16 27 16 17 23 17 18 23 18 19 30 19 20 9 20 21 19 21 22 30 22 23 20 23 24 8 24 25 29 25 26 18 26 27 34 27 28 4 28 29 47 29 30 36 30 31 32 ...
output:
12
result:
ok single line: '12'
Subtask #5:
score: 19
Accepted
Test #11:
score: 19
Accepted
time: 271ms
memory: 8196kb
input:
767 10000 5 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 2 1 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 21 1 21 22 1 22 23 1 23 24 1 24 25 1 25 13 1 26 27 1 27 28 1 28 29 1 29 30 1 30 31 1 31 32 1 32 33 1 33 34 1 34 35 1 35 36 1 36 37 1 37 38 1 38 39 1 39 40 1 ...
output:
1
result:
ok single line: '1'
Test #12:
score: 19
Accepted
time: 119ms
memory: 4752kb
input:
26 638 5 1 2 0 2 2 72 2 26 0 2 26 1 2 26 6 2 26 7 2 26 12 2 26 13 2 26 18 2 26 19 2 26 24 2 26 25 2 26 30 2 26 31 2 26 36 2 26 37 2 26 42 2 26 43 2 26 48 2 26 49 2 26 54 2 26 55 2 26 60 2 26 61 2 26 66 2 26 67 1 3 0 3 3 25 3 26 0 3 26 1 3 26 2 3 26 3 3 26 5 3 26 6 3 26 7 3 26 8 3 26 10 3 26 11 3 26 ...
output:
381798563
result:
ok single line: '381798563'
Test #13:
score: 19
Accepted
time: 165ms
memory: 4580kb
input:
25 628 5 1 2 0 2 2 90 2 25 0 2 25 2 2 25 5 2 25 6 2 25 7 2 25 8 2 25 10 2 25 11 2 25 12 2 25 14 2 25 17 2 25 18 2 25 19 2 25 21 2 25 26 2 25 27 2 25 28 2 25 29 2 25 30 2 25 32 2 25 35 2 25 36 2 25 37 2 25 38 2 25 40 2 25 41 2 25 42 2 25 44 2 25 47 2 25 48 2 25 49 2 25 51 2 25 56 2 25 57 2 25 58 2 25...
output:
672589923
result:
ok single line: '672589923'
Test #14:
score: 19
Accepted
time: 99ms
memory: 4844kb
input:
127 5541 5 2 2 2 2 127 0 2 127 1 3 3 3 3 127 0 3 127 2 4 4 5 4 127 0 4 127 2 5 5 7 5 127 0 5 127 1 5 127 2 5 127 4 5 127 5 5 127 6 6 6 11 6 127 1 6 127 2 6 127 4 6 127 6 6 127 7 6 127 9 7 7 13 7 127 8 8 8 17 8 127 0 8 127 1 8 127 4 8 127 6 8 127 8 8 127 10 8 127 12 8 127 13 8 127 15 8 127 16 9 9 19 ...
output:
1
result:
ok single line: '1'
Test #15:
score: 19
Accepted
time: 67ms
memory: 4564kb
input:
20 396 5 1 2 0 2 2 2 1 3 0 3 3 3 3 20 0 3 20 1 1 4 0 4 4 7 4 20 0 4 20 4 4 20 6 1 5 0 5 5 11 5 20 0 5 20 4 5 20 5 5 20 6 5 20 7 5 20 9 1 6 0 6 6 13 6 20 2 6 20 3 6 20 5 6 20 7 6 20 9 1 7 0 7 7 19 7 20 0 7 20 2 7 20 3 7 20 6 7 20 7 7 20 8 7 20 12 7 20 13 7 20 14 7 20 15 7 20 16 7 20 18 1 8 0 8 8 23 8...
output:
868803081
result:
ok single line: '868803081'
Subtask #6:
score: 9
Accepted
Test #16:
score: 9
Accepted
time: 58ms
memory: 4592kb
input:
25 596 6 1 2 0 2 2 16 2 25 2 2 25 4 2 25 5 2 25 6 2 25 7 2 25 8 2 25 9 2 25 10 2 25 11 2 25 12 2 25 13 2 25 14 1 3 0 3 3 64 3 25 0 3 25 1 3 25 2 3 25 6 3 25 7 3 25 8 3 25 9 3 25 10 3 25 14 3 25 15 3 25 16 3 25 17 3 25 18 3 25 22 3 25 23 3 25 24 3 25 25 3 25 26 3 25 30 3 25 31 3 25 32 3 25 33 3 25 34...
output:
7398268
result:
ok single line: '7398268'
Test #17:
score: 9
Accepted
time: 35ms
memory: 4480kb
input:
8 71 6 1 2 0 2 2 2 1 3 0 3 3 4 3 8 0 3 8 1 3 8 2 1 4 0 4 4 8 4 8 3 4 8 4 1 5 0 5 5 16 5 8 1 5 8 3 5 8 4 5 8 5 5 8 6 5 8 8 5 8 10 5 8 11 5 8 13 5 8 14 5 8 15 1 6 0 6 6 32 6 8 1 6 8 2 6 8 3 6 8 4 6 8 6 6 8 10 6 8 11 6 8 12 6 8 14 6 8 18 6 8 19 6 8 20 6 8 22 6 8 26 6 8 27 6 8 28 6 8 31 1 7 0 7 7 64 7 8...
output:
16
result:
ok single line: '16'
Test #18:
score: 9
Accepted
time: 85ms
memory: 6188kb
input:
14 189 6 1 2 0 2 2 3 1 3 0 3 3 7 3 14 2 3 14 5 3 14 6 1 4 0 4 4 8 4 14 0 4 14 2 4 14 7 1 5 0 5 5 11 5 14 2 5 14 6 1 6 0 6 6 25 6 14 2 6 14 3 6 14 4 6 14 7 6 14 8 6 14 9 6 14 12 6 14 13 6 14 14 6 14 18 6 14 19 6 14 22 6 14 23 6 14 24 1 7 0 7 7 29 7 14 2 7 14 3 7 14 4 7 14 7 7 14 11 7 14 13 7 14 16 7 ...
output:
714737421
result:
ok single line: '714737421'
Test #19:
score: 9
Accepted
time: 266ms
memory: 10500kb
input:
767 10000 6 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 2 1 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 21 1 21 22 1 22 23 1 23 24 1 24 25 1 25 13 1 26 27 1 27 28 1 28 29 1 29 30 1 30 31 1 31 32 1 32 33 1 33 34 1 34 35 1 35 36 1 36 37 1 37 38 1 38 39 1 39 40 1 ...
output:
1
result:
ok single line: '1'
Test #20:
score: 9
Accepted
time: 725ms
memory: 37308kb
input:
5000 10000 6 1 2 0 2 3 0 3 4 0 4 5 0 5 6 0 6 7 0 7 8 0 8 9 0 9 10 0 10 11 0 11 12 0 12 13 0 13 14 0 14 15 0 15 16 0 16 17 0 17 18 0 18 19 0 19 20 0 20 21 0 21 22 0 22 23 0 23 24 0 24 25 0 25 26 0 26 27 0 27 28 0 28 29 0 29 30 0 30 31 0 31 32 0 32 33 0 33 34 0 34 35 0 35 36 0 36 37 0 37 38 0 38 39 0 ...
output:
9
result:
ok single line: '9'
Subtask #7:
score: 18
Accepted
Test #21:
score: 18
Accepted
time: 21ms
memory: 6132kb
input:
15 133 7 1 2 0 2 2 5 2 15 1 2 15 3 2 15 4 1 3 0 3 3 8 3 15 2 3 15 3 3 15 6 1 4 0 4 4 9 4 15 3 4 15 4 4 15 5 4 15 7 1 5 0 5 5 10 5 15 2 5 15 4 5 15 6 5 15 7 5 15 8 5 15 9 1 6 0 6 6 12 6 15 2 6 15 4 6 15 5 6 15 9 6 15 10 6 15 11 1 7 0 7 7 13 7 15 0 7 15 1 7 15 2 7 15 3 7 15 5 7 15 6 7 15 7 7 15 9 7 15...
output:
1
result:
ok single line: '1'
Test #22:
score: 18
Accepted
time: 23ms
memory: 6320kb
input:
15 123 7 1 2 0 2 2 5 2 15 0 2 15 3 2 15 4 1 3 0 3 3 6 3 15 0 3 15 3 3 15 5 1 4 0 4 4 7 4 15 1 4 15 2 4 15 4 4 15 6 1 5 0 5 5 9 5 15 0 5 15 1 5 15 2 5 15 5 5 15 6 5 15 8 1 6 0 6 6 10 6 15 1 6 15 3 6 15 4 6 15 5 6 15 8 6 15 9 1 7 0 7 7 13 7 15 0 7 15 2 7 15 12 1 8 0 8 8 15 8 15 0 8 15 1 8 15 2 8 15 3 ...
output:
3063060
result:
ok single line: '3063060'
Test #23:
score: 18
Accepted
time: 22ms
memory: 4480kb
input:
11 89 7 1 2 0 2 2 5 2 11 1 2 11 3 2 11 4 1 3 0 3 3 8 3 11 0 3 11 2 3 11 3 3 11 4 3 11 6 1 4 0 4 4 9 4 11 0 4 11 1 4 11 2 4 11 5 4 11 7 1 5 0 5 5 12 5 11 1 5 11 3 5 11 7 5 11 8 5 11 10 5 11 11 1 6 0 6 6 14 6 11 0 6 11 3 6 11 4 6 11 6 6 11 7 6 11 8 6 11 9 6 11 13 1 7 0 7 7 19 7 11 0 7 11 3 7 11 4 7 11...
output:
3423420
result:
ok single line: '3423420'
Test #24:
score: 18
Accepted
time: 30ms
memory: 4540kb
input:
13 89 5 1 2 0 2 2 4 2 13 3 1 3 0 3 3 6 3 13 1 3 13 2 3 13 3 3 13 5 1 4 0 4 4 7 4 13 1 4 13 4 4 13 6 1 5 0 5 5 9 5 13 0 5 13 1 5 13 2 5 13 4 5 13 5 5 13 7 1 6 0 6 6 10 6 13 1 6 13 2 6 13 4 6 13 5 1 7 0 7 7 11 7 13 1 7 13 3 7 13 4 7 13 8 1 8 0 8 8 13 8 13 0 8 13 1 8 13 3 8 13 4 8 13 8 8 13 10 8 13 11 ...
output:
346393023
result:
ok single line: '346393023'
Test #25:
score: 18
Accepted
time: 22ms
memory: 4540kb
input:
14 122 7 1 2 0 2 2 4 2 14 1 2 14 2 2 14 3 1 3 0 3 3 6 3 14 0 3 14 4 1 4 0 4 4 7 4 14 1 4 14 2 4 14 3 1 5 0 5 5 9 5 14 1 5 14 2 5 14 3 5 14 8 1 6 0 6 6 10 6 14 1 6 14 2 6 14 3 6 14 6 6 14 7 6 14 9 1 7 0 7 7 15 7 14 0 7 14 2 7 14 4 7 14 5 7 14 6 7 14 7 7 14 9 7 14 11 7 14 13 7 14 14 1 8 0 8 8 17 8 14 ...
output:
528923553
result:
ok single line: '528923553'
Test #26:
score: 18
Accepted
time: 29ms
memory: 4548kb
input:
10 62 7 1 2 0 2 2 4 2 10 1 2 10 2 2 10 3 1 3 0 3 3 5 3 10 1 1 4 0 4 4 6 4 10 1 4 10 3 4 10 4 1 5 0 5 5 9 5 10 0 5 10 3 5 10 4 5 10 6 5 10 7 1 6 0 6 6 11 6 10 1 6 10 2 6 10 4 6 10 5 6 10 6 6 10 7 6 10 8 6 10 9 1 7 0 7 7 17 7 10 0 7 10 2 7 10 3 7 10 4 7 10 5 7 10 8 7 10 9 7 10 11 7 10 13 7 10 14 1 8 0...
output:
1492260
result:
ok single line: '1492260'
Test #27:
score: 18
Accepted
time: 694ms
memory: 34416kb
input:
5000 10000 7 1 2 0 2 3 0 3 4 0 4 5 0 5 6 0 6 7 0 7 8 0 8 9 0 9 10 0 10 11 0 11 12 0 12 13 0 13 14 0 14 15 0 15 16 0 16 17 0 17 18 0 18 19 0 19 20 0 20 21 0 21 22 0 22 23 0 23 24 0 24 25 0 25 26 0 26 27 0 27 28 0 28 29 0 29 30 0 30 31 0 31 32 0 32 33 0 33 34 0 34 35 0 35 36 0 36 37 0 37 38 0 38 39 0 ...
output:
3
result:
ok single line: '3'
Test #28:
score: 18
Accepted
time: 26ms
memory: 4632kb
input:
31 465 7 1 2 0 2 2 2 1 3 0 3 3 3 3 31 0 3 31 1 1 4 0 4 4 4 4 31 1 4 31 2 1 5 0 5 5 5 5 31 0 5 31 2 5 31 4 1 6 0 6 6 6 6 31 0 6 31 1 6 31 3 6 31 4 1 7 0 7 7 7 7 31 1 7 31 2 7 31 3 7 31 4 7 31 5 1 8 0 8 8 8 8 31 1 8 31 2 8 31 4 8 31 5 8 31 6 8 31 7 1 9 0 9 9 9 9 31 0 9 31 1 9 31 3 9 31 4 9 31 5 9 31 6...
output:
89541839
result:
ok single line: '89541839'
Test #29:
score: 18
Accepted
time: 26ms
memory: 4604kb
input:
31 451 7 1 2 0 2 2 2 2 31 1 1 3 0 3 3 3 3 31 0 3 31 2 1 4 0 4 4 4 4 31 0 4 31 1 4 31 3 1 5 0 5 5 5 5 31 0 5 31 1 5 31 2 5 31 3 1 6 0 6 6 6 6 31 0 6 31 1 6 31 2 6 31 3 6 31 5 1 7 0 7 7 7 7 31 0 7 31 2 7 31 3 7 31 4 7 31 5 1 8 0 8 8 8 8 31 0 8 31 1 8 31 3 8 31 4 8 31 5 8 31 6 8 31 7 1 9 0 9 9 9 9 31 0...
output:
160733989
result:
ok single line: '160733989'
Test #30:
score: 18
Accepted
time: 24ms
memory: 4432kb
input:
17 140 7 1 2 0 2 2 2 2 17 0 1 3 0 3 3 4 3 17 3 1 4 0 4 4 5 1 5 0 5 5 7 5 17 0 5 17 3 5 17 4 1 6 0 6 6 9 6 17 0 6 17 2 6 17 3 6 17 6 6 17 8 1 7 0 7 7 13 7 17 1 7 17 2 7 17 4 7 17 7 7 17 9 7 17 10 1 8 0 8 8 17 8 17 1 8 17 2 8 17 7 8 17 8 8 17 9 8 17 12 8 17 13 8 17 14 8 17 15 1 9 0 9 9 18 9 17 1 9 17 ...
output:
767157300
result:
ok single line: '767157300'
Test #31:
score: 18
Accepted
time: 23ms
memory: 4728kb
input:
20 186 7 1 2 0 2 2 2 1 3 0 3 3 4 3 20 0 3 20 3 1 4 0 4 4 5 4 20 1 4 20 4 1 5 0 5 5 8 5 20 3 5 20 5 5 20 6 1 6 0 6 6 10 6 20 1 6 20 2 6 20 3 6 20 4 6 20 8 1 7 0 7 7 13 7 20 0 7 20 1 7 20 2 7 20 4 7 20 5 7 20 8 7 20 10 1 8 0 8 8 14 8 20 1 8 20 2 8 20 6 8 20 8 8 20 12 1 9 0 9 9 17 9 20 4 9 20 5 9 20 11...
output:
362040671
result:
ok single line: '362040671'
Test #32:
score: 18
Accepted
time: 20ms
memory: 6300kb
input:
9 75 7 1 2 0 2 2 7 2 9 1 2 9 2 2 9 4 1 3 0 3 3 8 3 9 3 3 9 4 3 9 5 3 9 6 3 9 7 1 4 0 4 4 10 4 9 1 4 9 3 4 9 7 1 5 0 5 5 17 5 9 2 5 9 4 5 9 5 5 9 8 5 9 12 5 9 15 5 9 16 1 6 0 6 6 18 6 9 0 6 9 1 6 9 2 6 9 3 6 9 4 6 9 6 6 9 8 6 9 9 6 9 10 6 9 12 6 9 14 6 9 16 1 7 0 7 7 24 7 9 0 7 9 1 7 9 2 7 9 3 7 9 6 ...
output:
414120
result:
ok single line: '414120'
Test #33:
score: 18
Accepted
time: 116ms
memory: 9476kb
input:
1452 2220 7 1 525 0 525 925 1 925 1043 1 1043 825 0 825 831 0 831 804 1 804 121 1 121 1012 1 1012 1114 1 1114 1398 0 1398 264 1 264 235 0 235 1284 0 1284 1020 0 1020 792 0 792 375 1 375 885 1 885 1411 1 1411 1027 1 1027 857 0 857 180 1 180 1361 1 1361 565 1 565 1430 0 1430 404 1 404 1156 0 1156 646 ...
output:
7020
result:
ok single line: '7020'
Test #34:
score: 18
Accepted
time: 96ms
memory: 9468kb
input:
1452 2239 7 1 1117 1 1117 693 0 693 1182 1 1182 1200 1 1200 105 1 105 138 0 138 893 0 893 1136 0 1136 622 0 622 843 0 843 954 0 954 820 0 820 1139 1 1139 1362 0 1362 509 1 509 525 1 525 1381 1 1381 7 1 7 499 0 499 534 1 534 407 0 407 29 1 29 1436 1 1436 197 0 197 930 0 930 1410 0 1410 337 1 337 971 ...
output:
9828
result:
ok single line: '9828'
Test #35:
score: 18
Accepted
time: 327ms
memory: 21688kb
input:
4932 9860 7 1 872 1 872 900 0 900 1617 1 1617 3242 1 3242 380 0 380 178 1 178 3702 0 3702 4866 1 4866 4846 1 4846 1086 0 1086 41 1 41 1271 1 1271 4767 1 4767 3082 1 3082 3759 1 3759 2723 1 2723 1808 0 1808 2024 1 2024 971 0 971 3935 0 3935 665 0 665 2597 0 2597 3670 0 3670 387 0 387 1573 1 1573 2869...
output:
89541839
result:
ok single line: '89541839'
Subtask #8:
score: 24
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Dependency #7:
100%
Accepted
Test #36:
score: 24
Accepted
time: 240ms
memory: 19220kb
input:
3962 9999 8 1 1680 1 1680 3471 0 3471 720 1 720 2007 0 2007 3915 1 3915 133 0 133 3169 0 3169 2083 0 2083 3651 1 3651 2976 1 2976 1165 1 1165 3516 1 3516 3789 0 3789 653 1 653 208 1 208 3614 0 3614 1561 1 1561 1997 0 1997 973 1 973 365 0 365 609 0 609 1671 1 1671 1593 0 1593 2676 1 2676 1147 0 1147 ...
output:
794220612
result:
ok single line: '794220612'
Test #37:
score: 24
Accepted
time: 249ms
memory: 17632kb
input:
3962 9999 8 1 2711 0 2711 3474 1 3474 2084 0 2084 1854 0 1854 3779 1 3779 2180 0 2180 3507 0 3507 2960 1 2960 955 0 955 2600 0 2600 1585 0 1585 617 0 617 623 0 623 94 1 94 211 0 211 3649 1 3649 3123 1 3123 166 0 166 213 0 213 568 0 568 2679 1 2679 3588 1 3588 3800 1 3800 3033 1 3033 1170 1 1170 802 ...
output:
588441215
result:
ok single line: '588441215'
Test #38:
score: 24
Accepted
time: 109ms
memory: 4924kb
input:
201 7584 8 2 2 2 2 201 1 3 3 3 3 201 1 4 4 4 4 201 2 4 201 3 5 5 5 5 201 4 6 6 6 6 201 3 6 201 5 7 7 7 7 201 1 7 201 4 7 201 6 8 8 8 8 201 0 8 201 2 8 201 3 8 201 4 9 9 9 9 201 0 9 201 2 9 201 5 9 201 6 9 201 7 10 10 10 10 201 1 10 201 2 10 201 4 10 201 8 11 11 11 11 201 0 11 201 3 11 201 4 12 12 12...
output:
1
result:
ok single line: '1'
Test #39:
score: 24
Accepted
time: 39ms
memory: 8128kb
input:
14 345 8 1 2 0 2 2 5 1 3 0 3 3 6 3 14 0 3 14 1 3 14 2 3 14 5 1 4 0 4 4 20 4 14 0 4 14 1 4 14 2 4 14 4 4 14 5 4 14 10 4 14 11 4 14 13 4 14 15 4 14 16 4 14 17 4 14 19 1 5 0 5 5 34 5 14 1 5 14 2 5 14 4 5 14 5 5 14 8 5 14 9 5 14 10 5 14 11 5 14 13 5 14 20 5 14 21 5 14 22 5 14 23 5 14 25 5 14 26 5 14 28 ...
output:
670693521
result:
ok single line: '670693521'
Test #40:
score: 24
Accepted
time: 32ms
memory: 8212kb
input:
12 249 8 1 2 0 2 2 15 1 3 0 3 3 24 3 12 0 3 12 2 3 12 5 3 12 6 3 12 9 3 12 10 3 12 11 3 12 14 3 12 15 3 12 17 3 12 18 3 12 20 3 12 21 3 12 22 1 4 0 4 4 28 4 12 1 4 12 2 4 12 3 4 12 4 4 12 5 4 12 6 4 12 7 4 12 9 4 12 10 4 12 11 4 12 12 4 12 13 4 12 14 4 12 15 4 12 16 4 12 17 4 12 18 4 12 19 4 12 20 4...
output:
980169960
result:
ok single line: '980169960'
Test #41:
score: 24
Accepted
time: 44ms
memory: 6272kb
input:
16 261 8 1 2 0 2 2 2 2 16 0 1 3 0 3 3 4 1 4 0 4 4 15 4 16 1 4 16 4 4 16 7 4 16 10 4 16 13 1 5 0 5 5 17 5 16 1 5 16 3 5 16 5 5 16 6 5 16 7 5 16 9 5 16 10 5 16 14 5 16 15 1 6 0 6 6 21 6 16 3 6 16 4 6 16 6 6 16 7 6 16 12 6 16 13 6 16 14 6 16 15 6 16 16 6 16 17 1 7 0 7 7 38 7 16 1 7 16 4 7 16 6 7 16 7 7...
output:
700368949
result:
ok single line: '700368949'
Test #42:
score: 24
Accepted
time: 199ms
memory: 17708kb
input:
3962 5398 8 1 1387 0 1387 3656 1 3656 1250 1 1250 128 0 128 1202 0 1202 83 1 83 90 0 90 1218 0 1218 656 0 656 565 1 565 3670 1 3670 289 0 289 239 0 239 1109 1 1109 2050 0 2050 3844 1 3844 52 0 52 1562 1 1562 3686 0 3686 2596 1 2596 3035 0 3035 1365 0 1365 943 1 943 954 1 954 560 0 560 1204 0 1204 52...
output:
338765692
result:
ok single line: '338765692'
Test #43:
score: 24
Accepted
time: 274ms
memory: 21088kb
input:
4952 8000 8 1 2814 1 2814 3322 0 3322 3360 1 3360 1222 0 1222 4598 0 4598 4852 1 4852 3052 0 3052 663 1 663 3644 1 3644 4410 0 4410 4229 1 4229 4222 1 4222 217 1 217 2528 1 2528 1136 0 1136 2144 0 2144 1118 1 1118 323 0 323 1006 1 1006 3215 0 3215 3497 1 3497 3463 1 3463 2405 0 2405 456 0 456 4819 1...
output:
660
result:
ok single line: '660'
Test #44:
score: 24
Accepted
time: 278ms
memory: 21332kb
input:
4952 7588 8 1 511 0 511 4170 1 4170 1735 1 1735 2956 0 2956 2305 0 2305 4126 0 4126 4565 1 4565 2701 0 2701 766 1 766 759 0 759 1530 0 1530 1952 0 1952 752 1 752 677 0 677 2739 0 2739 149 1 149 2113 0 2113 4945 0 4945 3902 1 3902 2552 1 2552 4907 0 4907 2271 1 2271 4658 0 4658 1200 0 1200 2176 1 217...
output:
13712160
result:
ok single line: '13712160'
Test #45:
score: 24
Accepted
time: 658ms
memory: 37548kb
input:
5000 10000 8 1 2 0 2 3 0 3 4 0 4 5 0 5 6 0 6 7 0 7 8 0 8 9 0 9 10 0 10 11 0 11 12 0 12 13 0 13 14 0 14 15 0 15 16 0 16 17 0 17 18 0 18 19 0 19 20 0 20 21 0 21 22 0 22 23 0 23 24 0 24 25 0 25 26 0 26 27 0 27 28 0 28 29 0 29 30 0 30 31 0 31 32 0 32 33 0 33 34 0 34 35 0 35 36 0 36 37 0 37 38 0 38 39 0 ...
output:
4
result:
ok single line: '4'
Test #46:
score: 24
Accepted
time: 338ms
memory: 18700kb
input:
4951 10000 8 2 3 1 3 2 1 4 5 1 5 6 1 6 4 1 7 8 1 8 9 1 9 10 1 10 7 1 11 12 1 12 13 1 13 14 1 14 15 1 15 11 1 16 17 1 17 18 1 18 19 1 19 20 1 20 21 1 21 16 1 22 23 1 23 24 1 24 25 1 25 26 1 26 27 1 27 28 1 28 22 1 29 30 1 30 31 1 31 32 1 32 33 1 33 34 1 34 35 1 35 36 1 36 29 1 37 38 1 38 39 1 39 40 1...
output:
1
result:
ok single line: '1'
Test #47:
score: 24
Accepted
time: 27ms
memory: 4540kb
input:
13 334 8 1 2 0 2 2 10 2 13 0 2 13 1 2 13 2 2 13 3 2 13 5 2 13 6 2 13 7 2 13 9 1 3 0 3 3 15 3 13 0 3 13 3 3 13 4 3 13 5 3 13 7 3 13 8 3 13 9 3 13 14 1 4 0 4 4 21 4 13 0 4 13 1 4 13 2 4 13 3 4 13 7 4 13 12 4 13 13 4 13 14 4 13 16 4 13 17 1 5 0 5 5 23 5 13 3 5 13 5 5 13 6 5 13 7 5 13 9 5 13 10 5 13 11 ...
output:
837484870
result:
ok single line: '837484870'
Test #48:
score: 24
Accepted
time: 264ms
memory: 21012kb
input:
4952 7334 8 1 3824 0 3824 480 1 480 444 0 444 637 0 637 2312 1 2312 3356 0 3356 4210 1 4210 2721 1 2721 4781 0 4781 3785 1 3785 357 0 357 3055 0 3055 1686 0 1686 2951 0 2951 4331 0 4331 1313 1 1313 3564 1 3564 3337 0 3337 3344 1 3344 3667 0 3667 1044 0 1044 3490 1 3490 4907 0 4907 1070 0 1070 1737 1...
output:
117674516
result:
ok single line: '117674516'
Test #49:
score: 24
Accepted
time: 261ms
memory: 21008kb
input:
4952 7370 8 1 2579 1 2579 1964 1 1964 1371 1 1371 2599 0 2599 804 0 804 4618 0 4618 3004 1 3004 4230 1 4230 3411 0 3411 3143 0 3143 2458 0 2458 4734 1 4734 4628 0 4628 3284 1 3284 269 0 269 1978 0 1978 910 0 910 1989 1 1989 2327 0 2327 4011 0 4011 293 1 293 182 1 182 1070 1 1070 4505 1 4505 4870 0 4...
output:
308689785
result:
ok single line: '308689785'
Test #50:
score: 24
Accepted
time: 272ms
memory: 21204kb
input:
4952 7319 8 1 1538 0 1538 4513 0 4513 4932 0 4932 961 0 961 3337 1 3337 3413 1 3413 1373 1 1373 2702 0 2702 4299 1 4299 4938 0 4938 3207 0 3207 4694 0 4694 610 1 610 2244 1 2244 633 0 633 4800 1 4800 1007 1 1007 769 0 769 870 0 870 1555 0 1555 4758 1 4758 2327 0 2327 892 0 892 4187 0 4187 4823 0 482...
output:
506483589
result:
ok single line: '506483589'
Test #51:
score: 24
Accepted
time: 70ms
memory: 6000kb
input:
6 58 8 1 2 0 2 2 3 2 6 0 1 3 0 3 3 9 3 6 3 3 6 4 3 6 7 1 4 0 4 4 27 4 6 3 4 6 10 4 6 14 4 6 15 4 6 16 4 6 19 4 6 20 4 6 21 4 6 23 4 6 25 1 5 0 5 5 81 5 6 0 5 6 3 5 6 4 5 6 8 5 6 9 5 6 10 5 6 12 5 6 13 5 6 17 5 6 18 5 6 21 5 6 22 5 6 26 5 6 27 5 6 30 5 6 35 5 6 36 5 6 39 5 6 40 5 6 44 5 6 45 5 6 48 5...
output:
27
result:
ok single line: '27'
Test #52:
score: 24
Accepted
time: 23ms
memory: 4496kb
input:
12 158 8 1 2 0 2 2 3 2 12 0 2 12 2 1 3 0 3 3 9 3 12 3 3 12 6 3 12 8 1 4 0 4 4 27 4 12 1 4 12 4 4 12 5 4 12 8 4 12 12 4 12 14 4 12 16 4 12 17 4 12 19 4 12 20 4 12 22 4 12 25 1 5 0 5 5 81 5 12 0 5 12 1 5 12 3 5 12 4 5 12 5 5 12 6 5 12 9 5 12 10 5 12 12 5 12 13 5 12 14 5 12 15 5 12 18 5 12 19 5 12 21 5...
output:
1728
result:
ok single line: '1728'
Test #53:
score: 24
Accepted
time: 252ms
memory: 20916kb
input:
4952 7041 8 1 59 0 59 3267 1 3267 281 0 281 1741 0 1741 661 0 661 353 1 353 1581 0 1581 2179 0 2179 170 0 170 2693 1 2693 440 0 440 3281 1 3281 3177 1 3177 4515 1 4515 3680 1 3680 4205 0 4205 216 1 216 2913 1 2913 4872 1 4872 3483 0 3483 2286 0 2286 1877 0 1877 4743 0 4743 2441 0 2441 3266 0 3266 12...
output:
5400
result:
ok single line: '5400'
Test #54:
score: 24
Accepted
time: 22ms
memory: 4492kb
input:
10 186 8 1 2 0 2 2 7 2 10 0 2 10 1 2 10 2 2 10 3 2 10 4 2 10 6 1 3 0 3 3 10 3 10 0 3 10 1 3 10 2 3 10 3 3 10 4 3 10 5 3 10 8 3 10 9 1 4 0 4 4 30 4 10 0 4 10 1 4 10 3 4 10 4 4 10 5 4 10 7 4 10 8 4 10 9 4 10 11 4 10 13 4 10 14 4 10 16 4 10 17 4 10 21 4 10 22 4 10 24 4 10 25 4 10 26 4 10 27 4 10 28 4 1...
output:
243354720
result:
ok single line: '243354720'
Test #55:
score: 24
Accepted
time: 103ms
memory: 6516kb
input:
12 322 8 1 2 0 2 2 19 2 12 1 2 12 3 2 12 4 2 12 5 2 12 7 2 12 9 2 12 10 2 12 12 2 12 15 2 12 16 2 12 18 1 3 0 3 3 43 3 12 8 3 12 10 3 12 18 3 12 40 1 4 0 4 4 44 4 12 0 4 12 1 4 12 3 4 12 4 4 12 5 4 12 6 4 12 7 4 12 8 4 12 9 4 12 10 4 12 14 4 12 15 4 12 18 4 12 19 4 12 21 4 12 22 4 12 23 4 12 25 4 12...
output:
604422963
result:
ok single line: '604422963'
Extra Test:
score: 0
Extra Test Passed