Submission #531719

#TimeUsernameProblemLanguageResultExecution timeMemory
531719Killer2501Šarenlist (COCI22_sarenlist)C++14
35 / 110
3 ms412 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define ull unsigned long long #define pb push_back #define pll pair<ll, ll> #define pii pair<ll, int> #define fi first #define se second using namespace std; const int N = 65; const int M = 250; const ll mod = 1e9+7; const ll base = 75; const ll inf = 1e16; int n, lab[N], tong, t, c[N], h[N], P[N][8], m, a[N], b[N]; ll ans, d[N], k; vector<int> adj[N]; vector<pll> vi; string s; bool vis[N]; struct edge { int x, y, z; }e[N]; void add(ll& x, ll y) { x += y; if(x >= mod)x -= mod; } void dfs(int u, int p = 0) { for(int v: adj[u]) { if(v == p)continue; h[v] = h[u]+1; P[v][0] = u; for(int j = 1; j < 8; j ++)P[v][j] = P[P[v][j-1]][j-1]; dfs(v, u); } } int lca(int u, int v) { if(h[u] < h[v])swap(u, v); int log = log2(h[u]); for(int i = log; i >= 0; i --)if(h[u] >= h[v]+(1<<i))u = P[u][i]; if(u == v)return u; for(int i = log; i >= 0; i --) { if(P[u][i] && P[u][i] != P[v][i]) { u = P[u][i]; v = P[v][i]; } } return P[u][0]; } void cal(int u, int p = 0) { bool ok = false; for(int v: adj[u]) { if(v == p)continue; cal(v, u); c[u] += c[v]; ok |= (c[v] > 0); } if(c[u] == 0) { if(u > 1)++tong; if(ok)++tong; } } void sol() { cin >> n >> m >> k; for(int i = 1; i < n; i ++) { int x, y; cin >> x >> y; adj[x].pb(y); adj[y].pb(x); } d[0] = 1; for(int i = 1; i < n; i ++)d[i] = d[i-1] * k % mod; dfs(1); for(int i = 0; i < m; i ++) { cin >> e[i].x >> e[i].y; e[i].z = lca(e[i].x, e[i].y); } for(int mask = 0; mask < (1<<m); mask ++) { fill_n(c, n+1, 0); for(int i = 0; i < m; i ++) { if(mask >> i & 1) { ++c[e[i].x]; ++c[e[i].y]; c[e[i].z] -= 2; } } tong = 0; cal(1); //cout << mask <<" "<< __builtin_popcount(mask) <<" "<<tong << '\n'; if((__builtin_popcount(mask))&1)ans = (ans+mod-d[tong])%mod; else ans = (ans+d[tong])%mod; } cout << ans; } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); #define task "test" if(fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int test = 1; //cin >> test; while(test -- > 0)sol(); return 0; } /* 1234 21 */

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         freopen(task".out", "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...