QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #104063 | #6379. LaLa and Monster Hunting (Part 2) | chenshi | WA | 2ms | 3652kb | C++ | 2.2kb | 2023-05-08 14:19:47 | 2023-05-08 14:19:49 |
Judging History
answer
#include<cstdio>
using namespace std;
const int o=2e5+10,MOD=998244353;
int n,m,u[o],v[o],h[o],cnt=1,deg[o],H[o],Cnt,a[o],b[o],c[o],d[o],f[o],g,l[o],p[o],st[o],tp,col[o],id[o],asd,ans;
struct Edge{int v,p;}e[o],E[o];
inline void ad(int U,int V){e[++cnt].v=V;e[cnt].p=h[U];h[U]=cnt;}
inline void Ad(int U,int V){E[++Cnt].v=V;E[Cnt].p=H[U];H[U]=Cnt;}
inline bool cmp(int x,int y){if(deg[x]^deg[y]) return deg[x]<deg[y];return x<y;}
inline void calc(int x,int u,int y){
int t;
t=x*2+(e[x*2].v==u);c[t]=(c[t]+b[y]-1ll+MOD)%MOD;
t=y*2+(e[y*2].v==u);c[t]=(c[t]+b[x]-1ll+MOD)%MOD;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i) scanf("%d%d",&u[i],&v[i]),ad(++u[i],++v[i]),ad(v[i],u[i]),++deg[u[i]],++deg[v[i]];
for(int i=1;i<=m;++i) if(cmp(u[i],v[i])) Ad(u[i],v[i]);else Ad(v[i],u[i]);
for(int i=1;i<=m;++i){
++asd;
for(int j=H[u[i]];j;j=E[j].p) col[E[j].v]=asd,id[E[j].v]=j;
for(int j=H[v[i]];j;j=E[j].p) if(col[E[j].v]==asd)
++a[u[i]],++a[v[i]],++a[E[j].v],++b[i],++b[j],++b[id[E[j].v]];
}
for(int i=1;i<=m;++i){
++asd;
for(int j=H[u[i]];j;j=E[j].p) col[E[j].v]=asd,id[E[j].v]=j;
for(int j=H[v[i]];j;j=E[j].p) if(col[E[j].v]==asd)
calc(i,v[i],j),calc(j,E[j].v,id[E[j].v]),calc(id[E[j].v],u[i],i);
}
for(int i=1;i<=m;++i)
d[u[i]]=((d[u[i]]+a[v[i]])%MOD+MOD-b[i])%MOD,d[v[i]]=((d[v[i]]+a[u[i]])%MOD+MOD-b[i])%MOD;
for(int i=1;i<=n;++i) for(int j=h[i];j;j=e[j].p)
f[i]=(f[i]+0ll+d[e[j].v]+MOD-(a[i]+MOD-b[j/2])%MOD+MOD-c[j])%MOD;
for(int i=1;i<=n;++i) for(int j=h[i];j;j=e[j].p) ans=(ans+f[e[j].v]);
for(int i=1;i<=n;++i) ans=(ans+MOD-f[i])%MOD;
for(int i=1;i<=n;++i) g=(g+a[i]*(a[i]-1ll)/2)%MOD;
for(int i=1;i<=m;++i) g=(g+(MOD-b[i])*(b[i]-1ll))%MOD;
ans=(ans+(MOD-g)*4ll)%MOD;
for(int i=1;i<=n;++i){
for(int j=h[i];j;j=e[j].p) for(int k=H[e[j].v];k;k=E[k].p)
if(cmp(i,E[k].v)) if(!l[E[k].v]++) st[++tp]=E[k].v;
for(int j=h[i];j;j=e[j].p) for(int k=H[e[j].v];k;k=E[k].p)
if(cmp(i,E[k].v)) p[j/2]=(p[j/2]+l[E[k].v]-1)%MOD,p[k]=(p[k]+l[E[k].v]-1)%MOD;
for(;tp;l[st[tp--]]=0);
}
g=(MOD-g)*4ll%MOD;
for(int i=1;i<=m;++i) g=(g+p[i]*1ll*b[i])%MOD;
ans=(ans+(MOD-g)*2ll)%MOD;
printf("%d",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
input:
6 7 0 1 1 2 0 2 2 3 3 4 4 5 3 5
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
6 15 0 1 0 2 0 3 0 4 0 5 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
output:
360
result:
ok 1 number(s): "360"
Test #3:
score: 0
Accepted
time: 0ms
memory: 1516kb
input:
2 0
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3524kb
input:
2 1 0 1
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
2 1 0 1
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
2 1 0 1
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 1ms
memory: 1544kb
input:
2 0
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 2ms
memory: 3608kb
input:
2 1 0 1
output:
0
result:
ok 1 number(s): "0"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
3 3 1 2 0 2 0 1
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
3 2 0 1 0 2
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
3 2 0 2 0 1
output:
0
result:
ok 1 number(s): "0"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3552kb
input:
3 3 0 1 0 2 1 2
output:
0
result:
ok 1 number(s): "0"
Test #13:
score: 0
Accepted
time: 0ms
memory: 1752kb
input:
3 0
output:
0
result:
ok 1 number(s): "0"
Test #14:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
3 3 0 2 0 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #15:
score: -100
Wrong Answer
time: 1ms
memory: 3640kb
input:
4 5 0 3 0 2 1 3 0 1 1 2
output:
998244345
result:
wrong answer 1st numbers differ - expected: '0', found: '998244345'