QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #673215 | #4992. Enigmatic Enumeration | UZING | WA | 3ms | 4256kb | C++14 | 1.0kb | 2024-10-24 21:09:59 | 2024-10-24 21:10:05 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3005;
int n,m;
int u[N],v[N];
vector<int> g[N];
int dis[N];
ll dp[N];
ll ans;
int mis;
int flg[N][N];
queue<int> q;
void bfs(int st){
for(int i=1;i<=n;i++) dis[i]=N;
for(int i=1;i<=n;i++) dp[i]=0;
dis[st]=0; q.push(st); dp[st]=1;
while(!q.empty()){
int u=q.front(); q.pop();
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(flg[u][v]) continue;
if(dis[v]>dis[u]+1) {
dis[v]=dis[u]+1;
dp[v]=dp[u];
q.push(v);
}
else if(dis[v]==dis[u]+1) dp[v]+=dp[u];
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) {
scanf("%d%d",&u[i],&v[i]);
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
mis=N;
for(int i=1;i<=m;i++){
flg[u[i]][v[i]]=flg[v[i]][u[i]]=1;
bfs(u[i]);
if(dis[v[i]]==mis) ans+=dp[v[i]];
else if(dis[v[i]]<mis){
mis=dis[v[i]];
ans=dp[v[i]];
}
flg[u[i]][v[i]]=flg[v[i]][u[i]]=0;
}
ans/=(mis+1);
printf("%lld",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4160kb
input:
4 4 1 2 2 3 3 4 4 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
output:
10
result:
ok single line: '10'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
6 6 1 2 2 3 3 1 4 5 5 6 6 4
output:
2
result:
ok single line: '2'
Test #4:
score: -100
Wrong Answer
time: 3ms
memory: 4256kb
input:
110 5995 109 20 100 23 99 65 106 40 105 62 89 67 57 9 83 38 38 20 28 11 39 28 32 20 108 90 96 50 97 51 80 40 64 48 101 27 84 27 43 35 103 79 70 32 29 28 109 2 43 16 110 94 101 71 84 67 23 19 33 17 107 79 90 33 83 64 57 39 105 46 47 1 80 79 93 67 78 53 34 20 105 15 77 66 65 63 102 57 76 59 47 40 95 4...
output:
642
result:
wrong answer 1st lines differ - expected: '215820', found: '642'