QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #108362 | #6379. LaLa and Monster Hunting (Part 2) | zhanghaojie | WA | 3ms | 4484kb | C++14 | 3.2kb | 2023-05-24 19:20:55 | 2023-05-24 19:20:56 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod = 998244353;
typedef long long LL;
pair<int,int> edge[N];
int h[N],e[N],ne[N],w[N],idx;
int n,m,vis[N];
LL ans,v[N],ed[N],f[N],g[N],t[N],sum[N],cnt[N];
void add(int a,int b,int c){
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
a++,b++;
f[a]++,f[b]++;
edge[i]={a,b};
add(a,b,i),add(b,a,i);
}
for(int i=1;i<=n;i++)
{
for(int j=h[i];~j;j=ne[j])
if(f[e[j]]<f[i]||(f[e[j]]==f[i]&&i<e[j]))
vis[e[j]]=w[j];
for(int j=h[i];~j;j=ne[j])
if(f[e[j]]<f[i]||(f[e[j]]==f[i]&&i<e[j]))
{
int k=e[j];
for(int l=h[k];~l;l=ne[l])
if((f[e[l]]<f[k]||(f[e[l]]==f[k]&&k<e[l])) && vis[e[l]])
{
int ne=e[l];
// cout<<i<<' '<<k<<" "<<ne<<endl;
// cout<<vis[k]<<' '<<vis[ne]<<' '<<w[l]<<endl<<endl<<endl;
v[i]++,v[k]++,v[ne]++;
ed[vis[k]]++,ed[vis[ne]]++,ed[w[l]]++;
}
}
for(int j=h[i];~j;j=ne[j])
vis[e[j]]=0;
}
// for(int i=1;i<=n;i++)
// cout<<v[i]<<' ';
// cout<<endl;
// for(int i=1;i<=m;i++)
// cout<<ed[i]<<' ';
// cout<<endl;
for(int i=1;i<=n;i++)
{
for(int j=h[i];~j;j=ne[j])
g[i]=(g[i]+f[e[j]]-1)%mod;
}
for(int i=1;i<=n;i++)
{
for(int j=h[i];~j;j=ne[j])
t[i]=(t[i]+g[e[j]]-(f[i]-1))%mod;
t[i]=(t[i]-v[i]*2)%mod;
}
// cout<<endl<<endl;
// for(int i=1;i<=n;i++)
// cout<<f[i]<<' '<<g[i]<<' '<<t[i]<<endl;
for(int i=1;i<=n;i++)
ans=(ans+v[i]*t[i])%mod;
// cout<<ans<<endl;
for(int i=1;i<=n;i++)
{
for(int j=h[i];~j;j=ne[j])
if(f[e[j]]<f[i]||(f[e[j]]==f[i]&&i<e[j]))
vis[e[j]]=w[j];
for(int j=h[i];~j;j=ne[j])
if(f[e[j]]<f[i]||(f[e[j]]==f[i]&&i<e[j]))
{
int k=e[j];
for(int l=h[k];~l;l=ne[l])
if((f[e[l]]<f[k]||(f[e[l]]==f[k]&&k<e[l])) && vis[e[l]])
{
int ne=e[l];
ans=(ans-(g[k]-(f[i]-1)-ed[vis[k]]))%mod;
ans=(ans-(g[ne]-(f[k]-1)-ed[w[l]]))%mod;
ans=(ans-(g[i]-(f[ne]-1)-ed[vis[ne]]))%mod;
ans=(ans-(g[i]-(f[k]-1)-ed[vis[k]]))%mod;
ans=(ans-(g[k]-(f[ne]-1)-ed[w[l]]))%mod;
ans=(ans-(g[ne]-(f[i]-1)-ed[vis[ne]]))%mod;
ans=(ans-(ed[vis[k]]-1)*(f[k]-2))%mod;
ans=(ans-(ed[w[l]]-1)*(f[ne]-2))%mod;
ans=(ans-(ed[vis[ne]]-1)*(f[i]-2))%mod;
ans=(ans-(ed[vis[k]]-1)*(f[i]-2))%mod;
ans=(ans-(ed[w[l]]-1)*(f[k]-2))%mod;
ans=(ans-(ed[vis[ne]]-1)*(f[ne]-2))%mod;
ans=(ans+(ed[vis[k]]-1)*4)%mod;
ans=(ans+(ed[vis[ne]]-1)*4)%mod;
ans=(ans+(ed[w[l]]-1)*4)%mod;
}
}
for(int j=h[i];~j;j=ne[j])
vis[e[j]]=0;
}
for(int i=1;i<=n;i++)
{
for(int j=h[i];~j;j=ne[j])
if(f[e[j]]<=f[i]&&i<e[j])
{
int k=e[j];
for(int l=h[k];~l;l=ne[l])
if(i<e[l])
{
int ne=e[l];
ans=(ans-sum[ne]-cnt[ne]*2*(ed[w[j]]+ed[w[l]]))%mod;
sum[ne]=(sum[ne]+2*(ed[w[j]]+ed[w[l]]))%mod;
cnt[ne]=(cnt[ne]+1)%mod;
}
}
for(int j=h[i];~j;j=ne[j])
if(f[e[j]]<=f[i]&&i<e[j])
{
int k=e[j];
for(int l=h[k];~l;l=ne[l])
if(i<e[l])
{
int ne=e[l];
sum[ne]=cnt[ne]=0;
}
}
}
cout<<(ans+mod)%mod<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4476kb
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: 2ms
memory: 4188kb
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: 2ms
memory: 4220kb
input:
2 0
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 2ms
memory: 4296kb
input:
2 1 0 1
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 1ms
memory: 4256kb
input:
2 1 0 1
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 1ms
memory: 4304kb
input:
2 1 0 1
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 2ms
memory: 4160kb
input:
2 0
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 2ms
memory: 4428kb
input:
2 1 0 1
output:
0
result:
ok 1 number(s): "0"
Test #9:
score: 0
Accepted
time: 2ms
memory: 4320kb
input:
3 3 1 2 0 2 0 1
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 0ms
memory: 4176kb
input:
3 2 0 1 0 2
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: 0
Accepted
time: 2ms
memory: 4304kb
input:
3 2 0 2 0 1
output:
0
result:
ok 1 number(s): "0"
Test #12:
score: 0
Accepted
time: 2ms
memory: 4436kb
input:
3 3 0 1 0 2 1 2
output:
0
result:
ok 1 number(s): "0"
Test #13:
score: 0
Accepted
time: 2ms
memory: 4204kb
input:
3 0
output:
0
result:
ok 1 number(s): "0"
Test #14:
score: 0
Accepted
time: 0ms
memory: 4328kb
input:
3 3 0 2 0 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #15:
score: 0
Accepted
time: 0ms
memory: 4332kb
input:
4 5 0 3 0 2 1 3 0 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #16:
score: 0
Accepted
time: 0ms
memory: 4484kb
input:
4 3 2 3 1 2 0 2
output:
0
result:
ok 1 number(s): "0"
Test #17:
score: 0
Accepted
time: 2ms
memory: 4424kb
input:
4 1 2 3
output:
0
result:
ok 1 number(s): "0"
Test #18:
score: 0
Accepted
time: 2ms
memory: 4292kb
input:
4 3 2 3 1 2 0 3
output:
0
result:
ok 1 number(s): "0"
Test #19:
score: 0
Accepted
time: 2ms
memory: 4320kb
input:
4 5 1 2 0 3 1 3 0 1 0 2
output:
0
result:
ok 1 number(s): "0"
Test #20:
score: 0
Accepted
time: 0ms
memory: 4180kb
input:
4 4 2 3 0 3 1 3 0 2
output:
0
result:
ok 1 number(s): "0"
Test #21:
score: 0
Accepted
time: 3ms
memory: 4436kb
input:
5 6 2 4 0 3 1 4 2 3 0 4 0 2
output:
0
result:
ok 1 number(s): "0"
Test #22:
score: -100
Wrong Answer
time: 2ms
memory: 4360kb
input:
5 8 0 1 0 4 2 4 3 4 2 3 1 2 1 4 0 2
output:
76
result:
wrong answer 1st numbers differ - expected: '0', found: '76'