Submission #592139

#	Time	Username	Problem	Language	Result	Execution time	Memory
592139		jasmin	Star Trek (CEOI20_startrek)	C++14	15 / 100	1093 ms	576 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;
}

bool dfs(int v, int p, vector<vector<int> >& adi){

    for(auto u: adi[v]){
        if(u==p) continue;

        if(!dfs(u, v, adi)){
            return true;
        }
    }
    return false;
}

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

    int n, d;
    cin >>  n >> d;
    vector<vector<int> > adi(n*2);
    for(int i=0; i<n-1; i++){
        int a, b;
        cin >> a >> b;
        adi[a-1].push_back(b-1);
        adi[a-1+n].push_back(b-1+n);
        adi[b-1].push_back(a-1);
        adi[b-1+n].push_back(a-1+n);
    }

    int ans=0;
    if(n==2){
        ans=fastpow(4, d);
    }
    else{
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                adi[i].push_back(j+n);
                if(dfs(0, -1, adi)){
                    ans++;
                    //cout << i << " " << j << "\n";
                }
                adi[i].pop_back();
            }
        }
    }
    cout << ans << "\n";
}

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