Submission #481403

#	Time	Username	Problem	Language	Result	Execution time	Memory
481403		ArianKheirandish	Star Trek (CEOI20_startrek)	C++17	30 / 100	1 ms	588 KiB

startrek

//in the name of god//

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _			ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define all(x)		x.begin(),x.end()
#define F			first
#define S			second
#define MP			make_pair

const int maxn = 1e3 + 10;
const int mod = 1e9 + 7;

ll lchild[maxn], wchild[maxn], cnt, h[maxn], par[maxn], lo[maxn], lose, win, lrt[maxn];
vector<int> g[maxn];

ll pwr(ll a, ll b){
    if(!b)
        return 1;
    ll res = pwr(a, b >> 1);
    res = res * res % mod;
    if(b & 1)
        res = res * a % mod;
    return res;
}

void dfs(int v, int p) {
	par[v] = p;
	h[v] = h[p] + 1;
	int cntt = 0, ch = 0;
	for(auto i : g[v])
		if (i != p){
    		ch = ch + 1;
    		dfs(i, v);
    		cntt = cntt + lo[i];
    		if(lo[i])
    		    lchild[v] ++;
    		else
    		    wchild[v] ++;
	    }
	    
	if(!ch)
	    lo[v] = 1;
	else if(cntt)
	    lo[v] = 0;
	else
	    lo[v] = 1;
}
 
void dfss(int v, int p, int ted = 0) {
	if(ted == h[v] && lo[v])
	    cnt ++;
	    
	if(lo[v]){
	    for(auto i : g[v])
		    if (i != p)
			    dfss(i, v, ted + 1);
	}
	
	else{
		for(auto i : g[v])
			if(i != p){
    			if(lo[i]){
    				dfss(i, v, (lchild[v] == 1 ? ted + 1 : 0));
    		    }
		    }
	}
}
 
void dffs(int v, int p){
	lrt[v] = lo[v];
	if(lo[v])
	    lose = lose + 1;
	else
	    win = win + 1;
	    
	for(int i : g[v])
		if(i != p){
    		if(!lo[v] && lo[i]){
    			if(lchild[v] == 1 && (!lrt[par[v]])){
    				lo[v] = 1;
    				lo[i] = 0;
    				lchild[v] --;
    				lchild[i] ++;
    				dffs(i, v);
    				lo[v] = 0;
    				lo[i] = 1;
    				lchild[v] ++;
    				lchild[i] --;
    			}
    			else
    				dffs(i, v);
    		}
    		else
    			dffs(i, v);
    	}
}

int main(){_
    int n;
    ll d;
    cin >> n >> d;
    for(int i = 0 ; i < n - 1 ; i ++){
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    
    if(n == 2){
        cout << pwr(4, d) << '\n';
        return 0;
    }
    
	h[1] = -1;
	dfs(1, 1);
	dfss(1, 1);
	dffs(1, 1);
	
	if(lrt[1])
	    cout << 1ll * cnt * lose << '\n';
	else   
        cout << 1ll * n * win + 1ll * (n - cnt) * lose << '\n';
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15