Submission #531783

#TimeUsernameProblemLanguageResultExecution timeMemory
531783Killer2501Šarenlist (COCI22_sarenlist)C++14
35 / 110
1 ms332 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 int mod = 1e9+7; const ll base = 75; const ll inf = 1e16; int n, lab[N], t, c[N], h[N], P[N][8], m, a[N], b[N], ans, d[N], k; ll st[N], sum[N][8], tong; vector<int> adj[N]; vector<pll> vi; string s; bool vis[N]; struct edge { int x, y, z; }e[N]; void add(int& x, int 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; sum[v][0] = (1ll<<v); for(int j = 1; j < 8; j ++) { P[v][j] = P[P[v][j-1]][j-1]; sum[v][j] = (sum[v][j-1] | sum[P[v][j-1]][j-1]); } dfs(v, u); } } ll lca(int u, int v) { ll res = 0; 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)) { res |= sum[u][i]; u = P[u][i]; } } if(u == v)return res; for(int i = log; i >= 0; i --) { if(P[u][i] && P[u][i] != P[v][i]) { res |= sum[u][i]; res |= sum[v][i]; u = P[u][i]; v = P[v][i]; } } res |= sum[u][0]; res |= sum[v][0]; return res; } 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] = 1ll*d[i-1] * k % mod; dfs(1); for(int i = 0; i < m; i ++) { cin >> e[i].x >> e[i].y; st[i] = lca(e[i].x, e[i].y); //cout << st[i] <<" "; } //cout << '\n'; for(int mask = 0; mask < (1<<m); mask ++) { fill_n(c, n+1, 0); tong = 0; t = 0; for(int i = 0; i < m; i ++) { if(mask >> i & 1) { //cout << i <<" "; if((tong&st[i]) == 0)++t; tong |= st[i]; } } //cout <<t << '\n'; t += n-1-(__builtin_popcountll(tong)); if((__builtin_popcount(mask))&1)add(ans, mod-d[t]); else add(ans, d[t]); } 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:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         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...