QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #590631 | #4992. Enigmatic Enumeration | ship2077 | WA | 0ms | 4036kb | C++23 | 1.1kb | 2024-09-26 09:09:14 | 2024-09-26 09:09:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int M=5005;
vector<pair<int,int>>adj[M];
int n,m,Min=INT_MAX,cnt;
int x[M],y[M],dis[M],way[M];
int read(){
int x=0;char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
return x;
}
int main(){
n=read();m=read();
for (int i=1;i<=m;i++){
x[i]=read();y[i]=read();
adj[x[i]].emplace_back(y[i],i);
adj[y[i]].emplace_back(x[i],i);
}
for (int i=1;i<=m;i++){
const int s=x[i],t=y[i];
for (int i=1;i<=n;i++) dis[i]=-1,way[i]=0;
queue<int>q;q.emplace(s);
dis[s]=0;way[s]=1;
while (!q.empty()){
int x=q.front();q.pop();
for (auto [y,z]:adj[x]){ if (z==i) continue;
if (!~dis[y]) dis[y]=dis[x]+1,way[y]=way[x],q.emplace(y);
else if (dis[x]+1==dis[y]) way[y]+=way[x];
}
}
if (!~dis[t]) continue;
if (dis[t]+1<Min) Min=dis[t]+1,cnt=way[t];
else if (dis[t]+1==Min) cnt+=way[t];
}
printf("%d\n",cnt/Min);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4036kb
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: 3736kb
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: 3804kb
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: 0ms
memory: 3908kb
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:
2502
result:
wrong answer 1st lines differ - expected: '215820', found: '2502'