Submission #1048700

#TimeUsernameProblemLanguageResultExecution timeMemory
1048700antonAmusement Park (CEOI19_amusementpark)C++17
0 / 100
1 ms348 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> int N, M; const int MOD = 998244353; struct Edge{ int sides[2]; int dir= 0; Edge(){}; Edge(int a, int b){ sides[0] = a; sides[1] =b; } int dest(){ return sides[dir]; } int origin(){ return sides[dir^1]; } }; vector<vector<int>> adj; vector<Edge> edges; vector<int> ch(int i){ vector<int> res; for(auto eid : adj[i]){ Edge edge= edges[eid]; if(i == edge.origin()){ res.push_back(edge.dest()); } } return res; } bool is_DAG(int mask){ for(int i = 0; i<N; i++){ edges[i].dir = (mask>>i)& 1; } vector<int> free; vector<int> in_deg(N); for(int i = 0; i<N; i++){ for(auto c: ch(i)){ in_deg[c]++; } } for(int i = 0; i<N; i++){ if(in_deg[i]==0){ free.push_back(i); } } while(free.size()>0){ int i = free.back(); free.pop_back(); for(auto c: ch(i)){ in_deg[c]--; if(in_deg[c]==0){ free.push_back(c); } } } for(int i = 0; i<N; i++){ if(in_deg[i]>0){ return false; } } return true; } signed main(){ cin.tie(NULL); ios_base::sync_with_stdio(false); cin>>N>>M; adj.resize(N); for(int i = 0; i<M; i++){ int a, b; cin>>a>>b; a--;b--; edges.push_back(Edge(a, b)); adj[a].push_back(i); adj[b].push_back(i); } int RES =0; for(int mask =1; mask < (1<<M); mask++){ if(is_DAG(mask)){ //cout<<bitset<3>(mask)<<endl; RES = (RES + __builtin_popcount(mask)); } } cout<<RES<<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...