#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include "simurgh.h"
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
#define REP(i,a,b) for(ll i=(ll)a; i<(ll)b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 100000000
ll insig;
#define In(vecBRO, LENBRO) REP(IBRO,0,LENBRO) {cin>>insig; vecBRO.pb(insig);}
void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
ll N,M; vector<pl> ed; vector<ll> ans;
class Graph
{
public:
ll N;
vector<vector<ll> > adj;
vector<ll> visited; //for DFS/BFS
vector<ll> current; //for CC
vector<bool> c; //for Bip
bool bip; //for Bip
Graph() {ll N=0LL;}
Graph(vector<vector<ll> > ad)
{
adj=ad; N=adj.size(); REP(i,0,N) {visited.pb(false); c.pb(-1);}
}
void Reset()
{
REP(i,0,N) {visited[i]=false;}
current.clear();
}
void DFS(ll s)
{
if(visited[s]) {return;}
visited[s]=true;
current.pb(s); //only needed for CC
REP(i,0,adj[s].size())
{
if(!visited[adj[s][i]]) {c[adj[s][i]]=(c[s]+1)%2; DFS(adj[s][i]);}
else if(c[adj[s][i]]==c[s]) {bip=false;}
}
return;
}
bool Connected()
{
DFS(0);
REP(i,0,N) {if(!visited[i]) {return false;}}
return true;
}
vector<ll> BFS(ll s)
{
vector<ll> distance; REP(i,0,N) {distance.pb(INF);}
REP(i,0,N) {visited[i]=false;}
distance[s]=0; visited[s]=true;
deque<ll> d; d.pb(s); ll cur;
while(!d.empty())
{
cur=d.front(); d.pop_front();
REP(i,0,adj[cur].size())
{
if(!visited[adj[cur][i]])
{
visited[adj[cur][i]]=true;
d.pb(adj[cur][i]);
distance[adj[cur][i]]=distance[cur]+1;
}
}
}
return distance;
}
vector<pl> BFS_MS(vector<ll> sn) //multi-sourced BFS, ans[i].ff=d(i,starting nodes), ans[i].ss=starting node closer to i
{
ll K=sn.size();
vector<pl> distance; REP(i,0,N) {distance.pb(mp(INF,-1LL));}
REP(i,0,N) {visited[i]=false;}
REP(i,0,K) {distance[sn[i]]=mp(0LL,sn[i]); visited[sn[i]]=true;}
deque<ll> d; REP(i,0,K) {d.pb(sn[i]);} ll cur;
while(!d.empty())
{
cur=d.front(); d.pop_front();
REP(i,0,adj[cur].size())
{
if(visited[adj[cur][i]]) {continue;}
visited[adj[cur][i]]=true;
d.pb(adj[cur][i]);
distance[adj[cur][i]].ff=distance[cur].ff+1;
distance[adj[cur][i]].ss=distance[cur].ss;
}
}
return distance;
}
vector<vector<ll> > CC()
{
ll fi=0; ll missing=N; REP(i,0,N) {visited[i]=false;}
vector<vector<ll> > ans;
while(missing>0)
{
REP(i,fi,N) {if(!visited[i]) {fi=i; break;}}
current.clear();
DFS(fi);
ans.pb(current);
missing-=current.size();
}
return ans;
}
vector<Graph> CCG()
{
vector<Graph> ans;
vector<vector<ll> > CC=(*this).CC();
unordered_map<ll,ll> m;vector<ll> xx; vector<vector<ll> > ad;
REP(cc,0,CC.size())
{
m.clear();
ad.clear();
ll NN=CC[cc].size();
REP(i,0,NN) {ad.pb(xx);}
REP(i,0,NN) {m[CC[cc][i]]=i;}
ll a,b;
REP(i,0,NN)
{
a=CC[cc][i];
REP(j,0,adj[a].size()) {b=adj[a][j]; ad[i].pb(m[b]);}
}
Graph H(ad);
ans.pb(H);
}
return ans;
}
bool Bip()
{
c[0]=0;
bip=true;
DFS(0);
if(bip) {return true;}
else {return false;}
}
bool Eulerian()
{
REP(i,0,N) {if(adj[i].size()%2!=0) {return false;}}
return true;
}
};
void f(vector<int> a, ll c)
{
if(!ans.empty()) {return;}
if(a.size()==N-1)
{
int common = count_common_roads(a);
if(common==N-1) {ans=a; return;}
/*vector<vector<ll> > adj; vector<ll> xx; REP(i,0,N) {adj.pb(xx);}
REP(i,0,a.size())
{
adj[ed[a[i]].ff].pb(ed[a[i]].ss);
adj[ed[a[i]].ss].pb(ed[a[i]].ff);
Graph G(adj);
if(!G.Connected()) {return;}
int common = count_common_roads(a);
if(common==N-1) {ans=a; return;}
}*/
}
else
{
REP(i,c,M)
{
a.pb(i); f(a,i+1); a.pop_back();
}
}
}
vector<int> find_roads(int n, vector<int> u, vector<int> v)
{
N=(ll) n; M=u.size();
REP(i,0,M) {ed.pb(mp(u[i],v[i]));}
vector<int> em;
f(em,0LL);
return ans;
}
Compilation message
simurgh.cpp: In constructor 'Graph::Graph()':
simurgh.cpp:41:17: warning: unused variable 'N' [-Wunused-variable]
Graph() {ll N=0LL;}
^
simurgh.cpp: In function 'void f(std::vector<int>, ll)':
simurgh.cpp:176:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(a.size()==N-1)
~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
correct |
| 2 |
Incorrect |
4 ms |
256 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
