QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#668984 | #7302. Walk of Length 6 | Afterlife# | WA | 0ms | 3636kb | C++20 | 3.2kb | 2024-10-23 16:54:57 | 2024-10-23 16:54:57 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1007;
int n,m,deg[N];
bitset<N> e[N];
vector<int> g[N];
int f[N][N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
while(cin>>n)
{
for(int i=0;i<n;i++)
e[i].reset(),g[i].clear();
for(int i=0;i<n;i++)
{
string s;
cin>>s;
for(int j=0;j<n;j++)
if(s[j]=='1')
e[i].set(j,1),g[i].push_back(j),deg[i]++;
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
f[i][j]=(e[i]&e[j]).count();
int ans=0;
{
int m=0;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(e[i][j])
m++;
ans+=m*2;
}
{
for(int u=0;u<n;u++)
{
int c1=0,c2=0;
for(int v=0;v<n;v++)
{
if(u==v)
continue;
if(e[u][v])
{
c1+=f[u][v];
int t=f[u][v];
c2+=t*(t-1)/2;
}
}
c1/=2;
c1=c1*(c1-1)/2;
c1-=c2;
ans+=c1*24;
}
}
{
int cnt=0;
for(int u=0;u<n;u++)
for(int v=u+1;v<n;v++)
if(e[u][v])
cnt+=f[u][v];
ans+=cnt/3*24;
}
{
int cnt=0;
for(int u=0;u<n;u++)
for(int v=0;v<n;v++)
{
if(u==v)
continue;
int t=f[u][v];
cnt+=t*(t-1)/2*(deg[u]-2-(e[u][v]));
}
ans+=cnt*12;
}
{
int cnt=0;
for(int u=0;u<n;u++)
for(int v=u+1;v<n;v++)
if(e[u][v])
cnt+=((deg[u]-1)*(deg[v]-1)-f[u][v]);
ans+=cnt*6;
}
{
int cnt=0;
for(int u=0;u<n;u++)
for(int v=u+1;v<n;v++)
if(e[u][v])
{
int t=f[u][v];
cnt+=t*(t-1)/2;
}
ans+=cnt*36;
}
{
int cnt=0;
for(int u=0;u<n;u++)
for(int v=0;v<n;v++)
{
if(u==v)
continue;
int t=f[u][v];
cnt+=t*(t-1)/2;
}
ans+=cnt/4*48;
}
{
for(int u=0;u<n;u++)
{
ans+=deg[u]*(deg[u]-1)/2*12;
}
}
{
for(int u=0;u<n;u++)
{
ans+=deg[u]*(deg[u]-1)*(deg[u]-2)/6*12;
}
}
{
}
cout<<ans<<"\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3636kb
input:
3 011 101 110 4 0101 1010 0101 1010 6 011111 101111 110111 111011 111101 111110
output:
66 644 26094
result:
wrong answer 2nd numbers differ - expected: '128', found: '644'