Submission #696696

#	Time	Username	Problem	Language	Result	Execution time	Memory
696696		minhnhatnoe	Šarenlist (COCI22_sarenlist)	C++17	110 / 110	25 ms	324 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
vector<int> par;
vector<vector<int>> g;
void dfs(int v, int p){
    par[v] = p;
    for (int u: g[v]){
        if (u == p) continue;
        dfs(u, v);
    }
}
struct dsu{
    int c;
    vector<int> p;
    dsu(int n): p(n, -1), c(n) {}
    int find(int v){
        if (p[v] < 0) return v;
        return p[v] = find(p[v]);
    }
    void merge(int a, int b){
        a = find(a), b = find(b);
        if (a == b) return;
        if (-p[a] < -p[b]) swap(a, b);
        p[a] += p[b];
        p[b] = a;
        c--;
    }
    int get_co() {return c;}
    void merge_set(vector<int> &a){
        for (int i=1; i<a.size(); i++) merge(a[0], a[i]);
    }
};
ll binpow(ll a, ll b){
    ll r = 1;
    for (; b; b >>= 1, a = a*a % MOD)
        if (b & 1) r = r*a % MOD;
    return r;
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, m, k; cin >> n >> m >> k;
    g.resize(n), par.resize(n);
    for (int i=1; i<n; i++){
        int a, b; cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(0, -1);
    vector<vector<int>> sets(m);
    for (int i=0; i<m; i++){
        int a, b; cin >> a >> b;
        a--, b--;
        vector<int> l;
        while (a != -1){
            l.push_back(a);
            a = par[a];
        }
        vector<int> r;
        while (b != -1){
            r.push_back(b);
            b = par[b];
        }
        while (l.size() && r.size() && l.back() == r.back()) l.pop_back(), r.pop_back();
        sets[i].insert(sets[i].end(), l.begin(), l.end());
        sets[i].insert(sets[i].end(), r.rbegin(), r.rend());
    }
    ll result = 0;
    for (int i=(1<<m)-1; i>=0; i--){
        dsu ds(n);
        for (int j=0; j<m; j++){
            if (i & (1<<j)){
                ds.merge_set(sets[j]);
            }
            if (__builtin_parityll(i)){
                result -= binpow(k, ds.get_co()-1);
            }
            else{
                result += binpow(k, ds.get_co()-1);
            }
        }
    }
    cout << (result % MOD + MOD) % MOD << "\n";
}

Compilation message (stderr)

Main.cpp: In constructor 'dsu::dsu(int)':
Main.cpp:16:17: warning: 'dsu::p' will be initialized after [-Wreorder]
   16 |     vector<int> p;
      |                 ^
Main.cpp:15:9: warning:   'int dsu::c' [-Wreorder]
   15 |     int c;
      |         ^
Main.cpp:17:5: warning:   when initialized here [-Wreorder]
   17 |     dsu(int n): p(n, -1), c(n) {}
      |     ^~~
Main.cpp: In member function 'void dsu::merge_set(std::vector<int>&)':
Main.cpp:32:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (int i=1; i<a.size(); i++) merge(a[0], a[i]);
      |                       ~^~~~~~~~~

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