oj.uz

Submission #592158

# Submission time Handle Problem Language Result Execution time Memory
592158 2022-07-08T17:01:23 Z jasmin Star Trek (CEOI20_startrek) C++14
7 / 100
 1 ms 212 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long 

const int mod=1e9+7;

int fastpow(int a, int e){
    if(e==0) return 1;
    int ans=fastpow(a, e/2);
    ans=(ans*ans)%mod;
    if(e%2==1){
        ans=(ans*a)%mod;
    }
    return ans;
}

vector<int> parity;
void dfs(int v, int p, vector<vector<int> >& adi, int par, vector<bool> win){
    parity[v]=par;

    win[v]=false;
    for(auto u: adi[v]){
        if(u==p) continue;
        dfs(u, v, adi, 1-par, win);
        if(!win[u]){
            win[v]=true;
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, d;
    cin >>  n >> d;
    vector<vector<int> > adi(n);
    vector<vector<bool> > win(n, vector<bool> (n));
    vector<bool> w(n);
    parity.resize(n);
    for(int i=0; i<n-1; i++){
        int a, b;
        cin >> a >> b;
        adi[a-1].push_back(b-1);
        adi[b-1].push_back(a-1);
    }

    int ans=0;
    if(n==2){
        ans=fastpow(4, d);
    }
    else{
        for(int i=1; i<n; i++){
            dfs(i, -1, adi, 0, win[i]);
        }
        dfs(0, -1, adi, 0, win[0]);
        dfs(0, -1, adi, 0, w);
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                
                if(parity[i]==0 && (!win[j][j] || w[i])){
                    ans++;
                }
                else if(parity[i]==1 && (win[j][j] || !w[i])){
                    ans++;
                }
            }
        }
    }
    cout << ans << "\n";
}

Subtask #1
0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.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 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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -