## Submission #115896

# Submission time Handle Problem Language Result Execution time Memory
115896 2019-06-09T12:59:08 Z rajarshi_basu Potemkin cycle (CEOI15_indcyc) C++14
100 / 100
698 ms 6400 KB
```#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <stack>
#include <set>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double>
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>

using namespace std;

const int INF = 1e9+10;
const int MAXN = 1000+10;

int n,m;
bool mat[MAXN][MAXN];
int vis[MAXN][MAXN];
bool dvis[MAXN][MAXN];
bool validEdge[MAXN][MAXN];

stack<ii> cyc;
set<int> allnode;
bool done = 0;

inline bool isok(int a,int b,int c){
return (!(mat[a][b] and mat[b][c] and mat[a][c]));
}

void dfs1(ii node){
if(done)return;
cyc.push(node);
//cout << node.ff << " " << node.ss << endl;
if(vis[node.ff][node.ss]){
// we got our cycle
if(cyc.size() < 3){
cyc.pop();
return;
}
allnode.insert(node.ff);
allnode.insert(node.ss);
cyc.pop();
while(cyc.size() > 0){
ii x = cyc.top();cyc.pop();
//if(x.ff == x.ss)break;
//	cout <<x.ff << ' ' << x.ss << endl;
validEdge[x.ff][x.ss] = validEdge[x.ss][x.ff] = 1;
allnode.insert(x.ff);
allnode.insert(x.ss);
if(x.ff == node.ff and x.ss == node.ss)break;
}
done = 1;
return;
}

vis[node.ff][node.ss] = 1;
//vis[node.ss][node.ff] = 1;

FOR(nxt,n){
if(nxt == node.ff or node.ss == nxt)continue;
if(!mat[nxt][node.ss])continue;
if(isok(node.ff,node.ss,nxt)){
// this is a valid edge;
if(vis[node.ss][nxt] == 2)continue;
dfs1({node.ss,nxt});
//vis[node.ff][node.ss] = 0;

if(done)return;
}

}
vis[node.ff][node.ss] = 2;
if(cyc.size()>0)cyc.pop();
}

bool impNode[MAXN];
bool vis2[MAXN];
stack<int> st;
vector<int> cc;
void dfs2(int node,int p = -1){
if(done)return;
st.push(node);
//cout << node << endl;
vis2[node] = 1;
FOR(i,n){
if(node == i)continue;
if(p == i)continue;
if(done)return;

if(mat[node][i] and vis2[i] and impNode[i] and !validEdge[node][i]){
//st.pop();
while(!st.empty()){
int x = st.top();st.pop();
cc.pb(x);
if(x == i)break;
}
done = 1;
return;
}

if(validEdge[node][i]){
if(vis2[i]){
//st.pop();

while(!st.empty()){
int x = st.top();st.pop();
cc.pb(x);
if(x == i)break;
}
done = 1;
}else{
dfs2(i,node);
}

}
if(done)return;
}
if(st.size()>0)st.pop();
}

int main(){
cin >> n >> m;
FOR(i,n)FOR(j,n)mat[i][j] = validEdge[i][j] = vis[i][j] = 0;

FOR(i,m){
int a,b;
cin >> a >> b;
a--;b--;
mat[a][b] = mat[b][a] = 1;
}
// input done
FOR(i,n){
FOR(j,n)
if(!vis[i][j] and i != j and mat[i][j])
dfs1({i,j});

while(!cyc.empty())cyc.pop();
}
if(!done){
cout << "no" << endl;
return 0;
}

int x;
for(auto e:allnode){
impNode[e] = 1;
x = e;
}
/*
cout << endl;
for(auto e:allnode){
cout << e << endl;
}
cout << endl;
*/
FOR(i,n){
FOR(j,n){
if(validEdge[i][j] and !mat[i][j])return -1;
}
}

done = 0;

dfs2(x);

if(cc.empty()){
cout << "no" << endl;
}else{
FOR(i,cc.size()){

//if(!mat[cc[(i+cc.size()-1)%cc.size()]][cc[i]])return -1;
}
for(auto e:cc){
cout << e+1 << " ";
}

cout << endl;
}
return 0;
}```

### Compilation message

```indcyc.cpp: In function 'int main()':
indcyc.cpp:145:58: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
FOR(i,n)FOR(j,n)mat[i][j] = validEdge[i][j] = vis[i][j] = 0;
~~~~~~~~~~^~~
indcyc.cpp:17:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,n) for(int i=0;i<n;i++)
indcyc.cpp:191:7:
FOR(i,cc.size()){
~~~~~~~~~~~
indcyc.cpp:191:3: note: in expansion of macro 'FOR'
FOR(i,cc.size()){
^~~
indcyc.cpp:186:6: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
dfs2(x);
~~~~^~~```

#### Subtask #1 10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct

#### Subtask #2 10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 384 KB Output is correct

#### Subtask #3 10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

#### Subtask #4 10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 896 KB Output is correct

#### Subtask #5 10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1024 KB Output is correct
2 Correct 4 ms 1024 KB Output is correct

#### Subtask #6 10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2176 KB Output is correct
2 Correct 7 ms 2176 KB Output is correct
3 Correct 6 ms 2176 KB Output is correct
4 Correct 21 ms 2048 KB Output is correct

#### Subtask #7 10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2176 KB Output is correct
2 Correct 13 ms 2304 KB Output is correct

#### Subtask #8 10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 6312 KB Output is correct
2 Correct 54 ms 6272 KB Output is correct
3 Correct 371 ms 6308 KB Output is correct
4 Correct 146 ms 6400 KB Output is correct

#### Subtask #9 10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 6312 KB Output is correct
2 Correct 247 ms 6308 KB Output is correct

#### Subtask #10 10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 2944 KB Output is correct
2 Correct 256 ms 3064 KB Output is correct
3 Correct 129 ms 6272 KB Output is correct
4 Correct 698 ms 6392 KB Output is correct