Submission #696628

#TimeUsernameProblemLanguageResultExecution timeMemory
696628SanguineChameleonŠarenlist (COCI22_sarenlist)C++17
110 / 110
39 ms328 KiB
// BEGIN BOILERPLATE CODE #include <bits/stdc++.h> using namespace std; #ifdef KAMIRULEZ const bool kami_loc = true; const long long kami_seed = 69420; #else const bool kami_loc = false; const long long kami_seed = chrono::steady_clock::now().time_since_epoch().count(); #endif const string kami_fi = "kamirulez.inp"; const string kami_fo = "kamirulez.out"; mt19937_64 kami_gen(kami_seed); long long rand_range(long long rmin, long long rmax) { uniform_int_distribution<long long> rdist(rmin, rmax); return rdist(kami_gen); } long double rand_real(long double rmin, long double rmax) { uniform_real_distribution<long double> rdist(rmin, rmax); return rdist(kami_gen); } void file_io(string fi, string fo) { if (fi != "" && (!kami_loc || fi == kami_fi)) { freopen(fi.c_str(), "r", stdin); } if (fo != "" && (!kami_loc || fo == kami_fo)) { freopen(fo.c_str(), "w", stdout); } } void set_up() { if (kami_loc) { file_io(kami_fi, kami_fo); } ios_base::sync_with_stdio(0); cin.tie(0); } void just_do_it(); void just_exec_it() { if (kami_loc) { auto pstart = chrono::steady_clock::now(); just_do_it(); auto pend = chrono::steady_clock::now(); long long ptime = chrono::duration_cast<chrono::milliseconds>(pend - pstart).count(); string bar(50, '='); cout << '\n' << bar << '\n'; cout << "Time: " << ptime << " ms" << '\n'; } else { just_do_it(); } } int main() { set_up(); just_exec_it(); return 0; } // END BOILERPLATE CODE // BEGIN MAIN CODE const long long mod = 1e9 + 7; vector<pair<int, int>> adj[70]; vector<int> g[70]; bool f[70]; vector<int> cur; vector<vector<int>> paths; long long pw[70]; int fin; void dfs1(int u, int pr) { if (u == fin) { paths.push_back(cur); } for (auto x: adj[u]) { int v = x.first; int id = x.second; if (v != pr) { cur.push_back(id); dfs1(v, u); cur.pop_back(); } } } void dfs2(int u) { f[u] = true; for (auto v: g[u]) { if (!f[v]) { dfs2(v); } } } void just_do_it() { int n, m, k; cin >> n >> m >> k; pw[0] = 1; for (int i = 1; i <= n; i++) { pw[i] = pw[i - 1] * k % mod; } for (int i = 1; i <= n - 1; i++) { int u, v; cin >> u >> v; adj[u].push_back({v, i}); adj[v].push_back({u, i}); } for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; fin = v; dfs1(u, -1); } long long res = 0; for (int i = 0; i < (1 << m); i++) { for (int j = 1; j <= n - 1; j++) { g[j].clear(); f[j] = false; } int B = 0; for (int j = 0; j < m; j++) { if ((i >> j) & 1) { B++; int sz = paths[j].size(); for (int k = 0; k < sz - 1; k++) { int u = paths[j][k]; int v = paths[j][k + 1]; g[u].push_back(v); g[v].push_back(u); } } } int cnt = 0; for (int j = 1; j <= n - 1; j++) { if (!f[j]) { cnt++; dfs2(j); } } if (B & 1) { res = (res + mod - pw[cnt]) % mod; } else { res = (res + pw[cnt]) % mod; } } cout << res; } // END MAIN CODE

Compilation message (stderr)

Main.cpp: In function 'void file_io(std::string, std::string)':
Main.cpp:30:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   freopen(fi.c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   freopen(fo.c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...