Submission #130223

#TimeUsernameProblemLanguageResultExecution timeMemory
130223mechfrog88Paths (BOI18_paths)C++14
100 / 100
574 ms62484 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("unroll-loops,no-stack-protector") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; typedef long double ld; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); ll n,m,k; cin >> n >> m >> k; vector <ll> color(n+1); vector <vector<ll>> graph(n+1); for (int z=1;z<=n;z++){ cin >> color[z]; color[z]--; } for (int z=0;z<m;z++){ ll a,b; cin >> a >> b; graph[a].push_back(b); graph[b].push_back(a); } ll dp[n+1][1 << k] = {0}; for (int z=1;z<=n;z++){ dp[z][1 << color[z]] = 1; } for (int z=1;z<(1<<k);z++){ for (int x=1;x<=n;x++){ if (dp[x][z] < 1) continue; for (int q=0;q<graph[x].size();q++){ if (graph[x][q] == x) continue; ll v = graph[x][q]; if (z & (1 << color[v])) continue; dp[v][z | (1 << color[v])] += dp[x][z]; } } } ll count = 0; for (int z=1;z<=(1<<k);z++){ if (__builtin_popcount(z) == 1) continue; for (int x=1;x<=n;x++){ count += dp[x][z]; } } cout << count << endl; }

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:40:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int q=0;q<graph[x].size();q++){
                 ~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...