QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #840918 | #61. Cut Cut Cut! | lovely_ckj | WA | 3ms | 9652kb | C++14 | 1.3kb | 2025-01-03 10:02:22 | 2025-01-03 10:02:24 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <vector>
#include <random>
#include <cstdlib>
using namespace std;
const int S=100005,MS=25;
#define p 1000000007
int n,m;
vector<int> g[S];
mt19937 rnd(time(NULL));
int sm[S][MS],tmp[MS],a[S][MS][MS];
inline void add(int &x,int y)
{
x+=y;
if(x>=p) x-=p;
}
inline int qpow(int x,int y)
{
int res=1;
for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
return res;
}
inline void ins(int a[MS][MS],int x[])
{
for(int i=1;i<=MS-3;i++)
{
if(x[i]==0) continue;
if(a[i][i]==0)
{
for(int j=1;j<=MS-3;j++) a[i][j]=x[j];
a[0][0]++;
break;
}
int ml=1ll*x[i]*qpow(a[i][i],p-2)%p;
for(int j=1;j<=MS-3;j++)
add(x[j],p-1ll*a[i][j]*ml%p);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
for(int id=0;id<g[1].size();id++)
{
int v=g[1][id];
for(int i=1;i<=MS-3;i++) sm[v][i]=0;
sm[v][id+1]=rnd()%p;
ins(a[v],sm[v]);
}
for(int u=2;u<=n;u++)
{
printf("%d ",a[u][0][0]);
for(int v:g[u])
{
for(int i=1;i<=MS-3;i++)
{
tmp[i]=sm[u][i];
if(sm[u][i]!=0) add(tmp[i],rnd()%p);
}
for(int i=1;i<=MS-3;i++) add(sm[v][i],tmp[i]);
ins(a[v],tmp);
}
}
printf("\n");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 9032kb
input:
3 3 1 2 1 3 2 3
output:
1 2
result:
ok 2 number(s): "1 2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 9216kb
input:
8 8 1 2 1 3 1 5 2 4 2 5 3 6 4 5 7 8
output:
1 1 1 2 1 0 0
result:
ok 7 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 9652kb
input:
20 70 3 18 14 16 8 10 5 7 2 14 10 18 14 15 17 19 18 20 4 6 3 20 16 17 6 7 6 17 6 19 5 19 12 16 18 19 13 19 13 19 8 9 15 17 8 9 1 7 5 18 6 14 2 17 4 20 12 16 9 20 2 7 6 19 12 13 6 7 1 5 19 20 9 14 13 14 16 17 17 20 9 16 1 6 12 15 2 8 1 3 4 19 1 4 9 13 14 15 15 20 17 18 14 19 13 14 2 5 7 14 7 18 10 16...
output:
0 1 1 1 2 4 0 1 0 0 1 2 5 3 3 4 6 6 6
result:
ok 19 numbers
Test #4:
score: -100
Wrong Answer
time: 3ms
memory: 9216kb
input:
100 1000 26 51 88 93 96 97 55 92 49 60 89 92 81 84 87 95 80 96 33 81 48 73 12 91 71 86 89 90 33 78 13 100 60 89 45 48 98 100 10 43 40 50 13 29 96 99 83 92 84 85 20 39 97 100 41 76 51 71 28 61 2 80 57 89 58 83 10 30 21 85 1 21 86 95 1 65 66 78 57 91 30 41 46 72 59 64 59 79 17 33 68 79 45 78 8 91 12 7...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 1 1 1 1 1 1 2 3 0 1 3 3 0 2 4 1 4 3 2 1 3 1 4 4 3 2 4 4 4 3 4 4 4 5 2 5 3 7 7 5 6 4 7 7 6 7 6 4 5 7 7 7 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7
result:
wrong answer 53rd numbers differ - expected: '3', found: '4'