oj.uz

Submission #696696

# Submission time Handle Problem Language Result Execution time Memory
696696 2023-02-07T05:00:55 Z minhnhatnoe Šarenlist (COCI22_sarenlist) C++17
110 / 110
 25 ms 324 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 280 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 3 ms 212 KB Output is correct
6 Correct 3 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #5
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 280 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 2 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 3 ms 212 KB Output is correct
25 Correct 3 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 11 ms 212 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 14 ms 212 KB Output is correct
31 Correct 4 ms 324 KB Output is correct
32 Correct 2 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 6 ms 212 KB Output is correct
36 Correct 25 ms 212 KB Output is correct
37 Correct 12 ms 324 KB Output is correct