Submission #592157

#	Time	Username	Problem	Language	Result	Execution time	Memory
592157		jasmin	Star Trek (CEOI20_startrek)	C++14	7 / 100	1 ms	212 KiB

startrek

#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]){
                    ans++;
                }
                else if(parity[i]==1 && win[j][j]){
                    ans++;
                }
                else if(w[i]){
                    ans++;
                }
            }
        }
    }
    cout << ans << "\n";
}

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