oj.uz

Submission #481404

# Submission time Handle Problem Language Result Execution time Memory
481404 2021-10-20T16:35:13 Z ArianKheirandish Star Trek (CEOI20_startrek) C++17
30 / 100
 63 ms 15108 KB 
//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 = 1e5 + 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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Incorrect 2 ms 2764 KB Output isn't correct

Subtask #2
7.0 / 7.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 1 ms 2636 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 2 ms 2764 KB Output is correct
10 Correct 2 ms 2764 KB Output is correct
11 Correct 2 ms 2764 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 1 ms 2636 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 2 ms 2764 KB Output is correct
10 Correct 2 ms 2764 KB Output is correct
11 Correct 2 ms 2764 KB Output is correct
12 Incorrect 63 ms 15108 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 1 ms 2636 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 2 ms 2764 KB Output is correct
10 Correct 2 ms 2764 KB Output is correct
11 Correct 2 ms 2764 KB Output is correct
12 Correct 3 ms 2636 KB Output is correct
13 Incorrect 2 ms 2764 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 1 ms 2636 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 2 ms 2764 KB Output is correct
10 Correct 2 ms 2764 KB Output is correct
11 Correct 2 ms 2764 KB Output is correct
12 Incorrect 63 ms 15108 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Incorrect 2 ms 2764 KB Output isn't correct