Submission #796998

#	Time	Username	Problem	Language	Result	Execution time	Memory
796998		cig32	Šarenlist (COCI22_sarenlist)	C++17	110 / 110	58 ms	468 KiB

Main

#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
int n, m, k;
pair<int, int> edges[69];
int dsu[69];
int set_of(int u) {
  if(dsu[u] == u) return u;
  return dsu[u] = set_of(dsu[u]);
}
void union_(int u, int v) {
  dsu[set_of(u)] = set_of(v);
}
vector<pair<int,int> >adj[69];
int bruh[69][69];
bool dfs(int node, int prv, int tar, int id) {
  if(tar == node) return 1;
  for(pair<int,int>x:adj[node]){
    if(x.first==prv) continue;
    bool d=dfs(x.first,node,tar,id);
    if(d) {
      bruh[id][x.second]=1;
      return 1;
    }
  }
  return 0;
}
void solve(int tc) {
  cin >> n >> m >> k;
  for(int i=1; i<n; i++) {
    int u, v;
    cin >> u >> v;
    edges[i] = {u, v};
    adj[u].push_back({v, i});
    adj[v].push_back({u, i});
  }
  for(int i=1; i<=m; i++) {
    int a, b;
    cin >> a >> b;
    dfs(a, -1, b, i-1);
  }
  int ans = 0;
  for(int i=0; i<(1<<m); i++) {
    for(int j=1; j<n; j++) dsu[j] = j;
    for(int j=0; j<m; j++) {
      if(!(i & (1<<j))) continue;
      vector<int> v;
      for(int k=1; k<n; k++) if(bruh[j][k]) v.push_back(k);
      for(int k=1; k<v.size(); k++) union_(v[k-1], v[k]);
    }
    set<int>st;
    for(int j=1;j<n;j++)st.insert(set_of(j));
    int bruh = bm(k, st.size());
    if(__builtin_popcountll(i) & 1) ans = (ans+MOD-bruh) % MOD;
    else ans = (ans+bruh) % MOD;
  }
  cout << ans << '\n';
}
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
// 勿忘初衷

Compilation message (stderr)

Main.cpp: In function 'void solve(long long int)':
Main.cpp:68: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]
   68 |       for(int k=1; k<v.size(); k++) union_(v[k-1], v[k]);
      |                    ~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 65 / 65