Submission #1087336

#TimeUsernameProblemLanguageResultExecution timeMemory
1087336mychecksedadAmusement Park (CEOI19_amusementpark)C++17
0 / 100
1 ms348 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD1 (1000000000+7) #define MOD (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 100+100, M = 2e5+10, K = 52, MX = 30; int n, m, to[N][N]; ll dp[M], f[N]; void solve(){ cin >> n >> m; for(int i = 0; i <= n; ++i) for(int j = 0; j <= n; ++j) to[i][j] = 0; f[0] = 1; for(ll i = 1; i <= n; ++i) (f[i]=f[i-1]*i)%=MOD; for(int i = 1; i <= m; ++i){ int u, v; cin >> u >> v; --u, --v; to[u][v] = 1; to[v][u] = -1; } for(int mask = 0; mask < (1<<n); ++mask){ if(__builtin_popcount(mask) <= 1){ dp[mask] = 0; continue; } vector<int> v; dp[mask] = 0; for(int i = 0; i < n; ++i) if((1<<i)&mask) v.pb(i); int s = v.size(); for(int i = 0; i < v.size(); ++i){ ll cost = 0; for(int j: v){ if(v[i] != j){ if(to[v[i]][j] == 1) ++cost; } } dp[mask] += dp[mask^(1<<v[i])] + f[s - 1] * cost; dp[mask] %= MOD; } } cout << dp[(1<<n)-1]; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); en; } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }

Compilation message (stderr)

amusementpark.cpp: In function 'void solve()':
amusementpark.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i = 0; i < v.size(); ++i){
      |                    ~~^~~~~~~~~~
amusementpark.cpp: In function 'int main()':
amusementpark.cpp:56:15: warning: unused variable 'aa' [-Wunused-variable]
   56 |   int tt = 1, aa;
      |               ^~
#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...