Submission #59969

#TimeUsernameProblemLanguageResultExecution timeMemory
59969dukati8Duathlon (APIO18_duathlon)C++14
5 / 100
107 ms636 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...