Submission #863373

#TimeUsernameProblemLanguageResultExecution timeMemory
863373maks007Paths (BOI18_paths)C++14
23 / 100
3073 ms22608 KiB
// Bismi Allah #include "bits/stdc++.h" using namespace std; #define int long long signed main () { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m, k, ans = 0, changes = 1; cin >> n >> m >> k; vector <int> color(n), g[n], used(n), permutation(k); set <int> colorUsed; function <void(int, int)> dfs=[&](int v, int cur) { if(cur >= changes) { ans++; } if(cur == permutation.size() - 1) return; used[v] = 1; for(auto u : g[v] ) { if(!used[u] && color[u] == permutation[cur+1]) dfs(u, cur + 1); } used[v]=0; }; for(int i = 0; i < n; i ++) cin >> color[i]; for(int i = 0; i < m; i ++) { int u, v; cin >> u >> v; u --, v --; g[u].push_back(v); g[v].push_back(u); } vector <int> prev; for(int i = 0; i < k; i ++) permutation[i] = i + 1; do{ if(prev.size() > 0) { for(int i = 0; i < permutation.size(); i ++) { if(prev[i] != permutation[i]) { changes = i; break; } } changes = max(changes, 1LL); } for(int i = 0; i < n; i ++) { if(color[i] == permutation[0]) dfs(i, 0); } prev = permutation; } while(next_permutation(permutation.begin(), permutation.end())); cout << ans; return 0; }

Compilation message (stderr)

paths.cpp: In lambda function:
paths.cpp:19:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   if(cur == permutation.size() - 1) return;
      |      ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
paths.cpp: In function 'int main()':
paths.cpp:39:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    for(int i = 0; i < permutation.size(); i ++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...