Submission #932407

#TimeUsernameProblemLanguageResultExecution timeMemory
932407a_l_i_r_e_z_aAmusement Park (CEOI19_amusementpark)C++17
42 / 100
2403 ms35400 KiB
// In the name of God // Hope is last to die #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define pb push_back #define int long long #define S second #define F first #define mp make_pair #define smax(x, y) (x) = max((x), (y)) #define smin(x, y) (x) = min((x), (y)) #define all(x) (x).begin(), (x).end() #define len(x) ((int)(x).size()) const int maxn = 11; const int inf = 1e9 + 7, mod = 998244353; int n, m, in[maxn], deg[maxn]; vector<int> adj[maxn], g[maxn]; int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; set<int> st; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; adj[u].pb(v); } vector<int> A; do{ for(int i = 0; i < n; i++){ in[a[i]] = i; deg[i + 1] = 0; g[i + 1].clear(); } for(int i = 1; i <= n; i++){ for(auto u: adj[i]){ if(in[i] > in[u]){ g[u].pb(i); deg[i]++; } else{ g[i].pb(u); deg[u]++; } } } for(int i = 1; i <= n; i++) if(!deg[i]) st.insert(i); int x = 0; while(st.size()){ int v = (*st.begin()); x *= 10; x += v - 1; st.erase(st.begin()); for(auto u: g[v]){ deg[u]--; if(!deg[u]) st.insert(u); } } A.pb(x); } while (next_permutation(a, a + n)); sort(all(A)); A.resize(unique(all(A)) - A.begin()); ll ans = 0; for(auto &per: A){ for(int i = 0; i < n; i++){ in[per % 10 + 1] = n - i; per /= 10; } for(int i = 1; i <= n; i++){ for(auto u: adj[i]) if(in[u] < in[i]) ans++; } } cout << ((ans) % mod) << '\n'; return 0; }
#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...