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 int long long
#define double long double
#define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d))
#define szof(x) ((int)(x).size())
#define vi vector<int>
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
int n, m;
vector<pii> edges;
int res;
void check(int mask){
bool edge[20][20];
int indeg[20];
int val = 0;
FOR(i, 1, n, 1){
indeg[i] = 0;
FOR(j, 1, n, 1){
edge[i][j] = 0;
}
}
FOR(i, 0, m-1, 1){
if( (mask & (1<<i)) == 0 ){
edge[ edges[i].F ][ edges[i].S ] = 1;
indeg[ edges[i].S ]++;
}
else{
edge[ edges[i].S ][ edges[i].F ] = 1;
indeg[ edges[i].F ]++;
val++;
}
}
vi qu;
int vis = 0;
FOR(i, 1, n, 1){
if(indeg[i] == 0){
qu.pb(i);
vis++;
}
}
while( !qu.empty() ){
int v = qu.back();
qu.pop_back();
FOR(i, 1, n, 1){
if(edge[v][i] == 1){
indeg[i]--;
if(indeg[i] == 0){
qu.pb(i);
vis++;
}
}
}
}
if(vis == n){
res += val;
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
edges.resize(m);
FOR(i, 0, m-1, 1){
cin>>edges[i].F>>edges[i].S;
}
res = 0;
FOR(mask, 0, (1<<m)-1, 1){
check(mask);
}
cout<<res<<'\n';
return 0;
}
# | 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... |