This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a; i<int(b); i++)
#define all(x) x.begin(),x.end()
bool flags[100000];
bool visits[100000];
vector<pair<int,int> > roads;
vector< vector<int> > close;
bool dfs(int curr, int goal) {
if (curr==goal) {flags[curr]=true; return true;}
visits[curr]=true;
for (auto a:close[curr]) {
if (!visits[a]) {
if (dfs(a,goal)) {flags[curr]=true; return true;}
}
}
return false;
}
bool bfs(int start, int goal) {
queue<int> order;
order.push(start);
int from[60];
while (!order.empty()) {
int now = order.front();
order.pop();
if (now==goal) {
flags[now]=true;
while (now!=start){
now=from[now];
flags[now]=true;
}
return true;
}
for (auto a:close[now]) {
if (!visits[a]) {
from[a]=now;
order.push(a);
visits[a]=true;
}
}
}
return false;
}
int main() {
int n,m;
cin >>n >>m;
if (n<=50) {
close.assign(n,vector<int>());
rep(i,0,m) {
int u,v;
cin >> u >> v;
u--;v--;
roads.push_back(make_pair(u,v));
close[u].push_back(v);
close[v].push_back(u);
}
int count=0;
rep(i,0,n) {
rep (j,0,n) {
rep (k,0,n) {
if (i!=j && j!=k && i!=k) {
//search route i to j and j to k, and if not works try other way instead.
rep (x,0,n) {visits[x]=false; flags[x]=false;}
if (bfs(i,j)) {
rep (x,0,n) visits[x]=flags[x];
if (bfs(j,k)) {count++;}
else {
rep (x,0,n) {visits[x]=false; flags[x]=false;}
if (bfs(j,k)) {
rep (x,0,n) visits[x]=flags[x];
if (bfs(j,i)) {count++;}
}
}
}
}
}
}
}
cout << count << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |