oj.uz

Submission #880632

# Submission time Handle Problem Language Result Execution time Memory
880632 2023-11-29T18:46:54 Z tsumondai Šarenlist (COCI22_sarenlist) C++14
10 / 110
 4 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 60;
 
const int oo = 1e9, mod = 1e9 + 7;
 
int n, m, k, parent[N], depth[N], path[N], uf[N], union_mask[N];
vector<int> adj[N];

int add(int a, int b) {
	a+=b;
	if (a>=mod) a-=mod;
	return a;
}

int sub(int a, int b) {
	a-=b;
	if (a<0) a+=mod;
	return a;
}

int mul(int a, int b) {
	return (a*b)%mod;
}

long long binpow(long long a, long long b) {
    a %= mod;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void dfs(int node, int p=-1, int d=0){
    parent[node] = p;
    depth[node] = d;
    for(int i:adj[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 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 -= __builtin_popcount(union_mask[i]);
    }
    return binpow(k, cnt+not_on_paths);
}

void process() {
	cin >> n >> m >> k;
	foru(i,1,n-1) {
		int u, v; cin >> u >> v;
		adj[u].pb(v); adj[v].pb(u);
	}
	dfs(1);
	foru(i,0,m-1) {
		int c, d; cin >> c >> d;
		mark_path(i, c, d);
	}
	int res=0;
	foru(mask, 0, (1<<m)-1) {
		int popcorn=__builtin_popcount(mask);
		if (popcorn%2==0) {
			res=add(res, compute(mask));
		} else {
			res=sub(res, compute(mask));
		}
	}
	cout << res;
    return;
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    process();
    cerr << "Time elapsed: " << __TIME << " s.\n";
    return 0;
}

/*
Xét các trường hợp đặc biệt
Kiểm tra lại input/output
Cố gắng trâu
Lật ngược bài toán
Keep calm and get VOI 
Flow:

*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -