Submission #533557

#TimeUsernameProblemLanguageResultExecution timeMemory
533557N1NT3NDOŠarenlist (COCI22_sarenlist)C++14
10 / 110
72 ms316 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> #define sz(x) (int)x.size() #define fi first #define sd second #define all(x) x.begin(), x.end() //#pragma GCC target ("avx2") //#pragma GCC optimization ("O3") //#pragma GCC optimization ("unroll-loops") using namespace std; //using namespace __gnu_pbds; //typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; const ll mod = 1e9 + 7; const int N = 70; vector<int> g[N]; int n, m, len[N][N], who, l[N], r[N], col[N], F; ll k, ans; vector< pair< int, int> > vec; bool ok = 0; void dfs(int v, int pr, vector<int> vc) { if (v == F) { set<int> se; for(auto u : vc) se.insert(u); if (sz(se) >= 2) ok = 1; return; } for(int i = 0; i < sz(vec); i++) { int a = vec[i].fi, b = vec[i].sd; if (v != a && v != b) continue; if (v == a && b != pr) { vc.pb(col[i]); dfs(b, v, vc); vc.pop_back(); } else if (b == v && a != pr) { vc.pb(col[i]); dfs(a, v, vc); vc.pop_back(); } } } ll f(ll x) { ll res = 1; for(ll i = 2; i <= x; i++) res = (res * i) % mod; return res; } void group4() { int ans = 0; for(int mask = 0; mask < (1 << sz(vec)); mask++) { for(int i = 0; i < sz(vec); i++) if (mask & (1 << i)) col[i] = 1; else col[i] = 2; bool bad = 0; for(int i = 1; i <= m; i++) { ok = 0; F = r[i]; dfs(l[i], l[i], {}); if (!ok) { bad = 1; break; } } if (!bad) ans++; } cout << ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k; for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; g[u].pb(v); g[v].pb(u); vec.pb({u, v}); } for(int i = 1; i <= m; ++i) cin >> l[i] >> r[i]; if (n <= 15 && k == 2) group4(); }
#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...