Submission #864488

#TimeUsernameProblemLanguageResultExecution timeMemory
864488RequiemAmusement Park (CEOI19_amusementpark)C++17
19 / 100
3060 ms600 KiB
#include<bits/stdc++.h> #define int long long #define pb push_back #define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); #define MOD 998244353 #define INF 1e18 #define fi first #define se second #define endl "\n" #define FOR(i,a,b) for(int i=a;i<=b;i++) #define FORD(i,a,b) for(int i=a;i>=b;i--) #define sz(a) ((int)(a).size()) #define pi 3.14159265359 #define TASKNAME "amusepark" template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; } template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; } using namespace std; typedef pair<int,int> ii; typedef pair<int,ii> iii; typedef vector<int> vi; const int MAXN = 3e2 + 9; ii edge[MAXN]; int n,m,ans=0; int degree[MAXN]; vector<int> g[MAXN]; bool visited[MAXN]; queue<int> q; bool check(){ for(int i=1;i<=n;i++){ degree[i] = 0; g[i].clear(); } for(int i=1;i<=m;i++){ g[edge[i].fi].pb(edge[i].se); degree[edge[i].se]++; // cout<<edge[i].fi<<' '<<edge[i].se<<endl; } int cnt = 0; // cout<<endl<<endl; for(int i=1;i<=n;i++){ if (degree[i] == 0) q.push(i); } while(!q.empty()){ int u = q.front(); cnt++; q.pop(); for(auto v: g[u]){ degree[v]--; if (degree[v] == 0) q.push(v); } } return cnt == n; } void backtrack(int pos,int cost){ if (pos==m+1){ if (check()){ ans = (ans + cost)%MOD; } return; } swap(edge[pos].fi,edge[pos].se); backtrack(pos+1,cost+1); swap(edge[pos].fi,edge[pos].se); backtrack(pos+1,cost); } main() { fast; // freopen(TASKNAME".inp","r",stdin); // freopen(TASKNAME".out","w",stdout); cin>>n>>m; for(int i=1;i<=m;i++){ cin>>edge[i].fi>>edge[i].se; } backtrack(1,0); cout<<ans<<endl; }

Compilation message (stderr)

amusementpark.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main()
      | ^~~~
#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...