제출 #1048775

#제출 시각아이디문제언어결과실행 시간메모리
1048775antonAmusement Park (CEOI19_amusementpark)C++17
19 / 100
58 ms10112 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<M; 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; } int get_mask(vector<int>& order){ int res = 0; for(int i = 0; i<M; i++){ Edge e= edges[i]; if(order[e.sides[0]]>order[e.sides[1]]){ res |= (1<<i); } } return res; } unordered_set<int> get_valid_masks(){ vector<int> order; for(int i = 0; i<N; i++){ order.push_back(i); } bool ok = true; unordered_set<int> masks; while(ok){ masks.insert(get_mask(order)); ok = next_permutation(order.begin(), order.end()); } return masks; } 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(auto mask: get_valid_masks()){ //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...