oj.uz

Submission #525984

# Submission time Handle Problem Language Result Execution time Memory
525984 2022-02-13T11:59:21 Z model_code Šarenlist (COCI22_sarenlist) C++17
110 / 110
 15 ms 280 KB 
#include <cstdio>
#include <vector>


using namespace std;


const int MAXN = 61;
const int MAXM = 16;
const int MOD = 1000000007;

int n,m,k;
vector<int> graph[MAXN];
int depth[MAXN];
int parent[MAXN];
long long path[MAXM];

int popcount(long long x){
    int res=0;
    for(;x;x>>=1){
        if(x&1) res++;
    }
    return res;
}

int ADD(long long a, long long b){
    return (a+b)%MOD;
}
int SUB(long long a, long long b){
    return (a+MOD-b)%MOD;
}
int MUL(long long a, long long b){
    return a*b%MOD;
}
int EXP(long long a, long long b){
    if(b==0) return 1;
    if(b%2==1) return MUL(a, EXP(a, b-1));
    else return EXP(MUL(a, a), b/2);
}

void dfs(int node, int p=-1, int d=0){
    parent[node] = p;
    depth[node] = d;
    for(int i:graph[node]){
        if(i != p) dfs(i, node, d+1);
    }
}
void mark_path(int idx, int u, int v){
    if(depth[u] < depth[v]) swap(u, v);
    for(;depth[u] > depth[v];u = parent[u]){
        path[idx] |= (1LL<<u);
    }
    for(;u != v;u=parent[u],v=parent[v]){
        path[idx] |= (1LL<<v);
        path[idx] |= (1LL<<u);
    }
}

int uf[MAXM];
long long union_mask[MAXM];
int fnd(int a){
    return uf[a]=(uf[a]==a?a:fnd(uf[a]));
}
void un(int a, int b){
    a=fnd(a);
    b=fnd(b);
    uf[a]=b;
    union_mask[b] |= union_mask[a];
}
void reset_uf(){
    for(int i=0;i<m;i++) uf[i] = i;
    for(int i=0;i<m;i++) union_mask[i] = path[i];
}

int compute(int mask){
    reset_uf();
    for(int i=0;i<m;i++){
        if(!(mask & (1<<i))) continue;
        for(int j=i+1;j<m;j++){
            if(!(mask & (1<<j))) continue;
            if(path[i] & path[j]){
                un(i, j);
            }
        }
    }
    int cnt = 0;
    int not_on_paths=n-1;
    for(int i=0;i<m;i++){
        if(!(mask & (1<<i))) continue;
        if(i != uf[i]) continue;
        cnt++;
        not_on_paths -= popcount(union_mask[i]);
    }
    //printf("%d %d %d\n", mask, cnt, not_on_paths);
    return EXP(k, cnt+not_on_paths);
}

int main(){
    scanf("%d%d%d", &n, &m, &k);
    for(int i=0;i<n-1;i++){
        int a,b;
        scanf("%d%d", &a, &b);
//        a--;b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    dfs(1);
    for(int i=0;i<m;i++){
        int c,d;
        scanf("%d%d", &c, &d);
//        c--;d--;
        mark_path(i, c, d);
    }
    int res=0;
    for(int mask=0;mask<(1<<m);mask++){
        int popcount = __builtin_popcount(mask);
        if(popcount % 2 == 0){
            res=ADD(res, compute(mask));
            //printf("%d +%d\n", mask, compute(mask));
        }else{
            res=SUB(res, compute(mask));
            //printf("%d -%d\n", mask, compute(mask));
        }
    }
    printf("%d\n", res);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     scanf("%d%d%d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         scanf("%d%d", &c, &d);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
65.0 / 65.0

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