Submission #757574

#	Time	Username	Problem	Language	Result	Execution time	Memory
757574		gagik_2007	Star Trek (CEOI20_startrek)	C++17	7 / 100	15 ms	5200 KiB

startrek

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=1007;
ll n,m,k;
vector<int>g[N];
bool dp[N][N]; // i - root, j - vertex (0: mtnoxy krvuma, 1: mtnoxy kruma)
bool tmp[N];
int cnt[N][N];
int p[N];

ll binpow(ll x, ll y){
    if(y==0)return 1;
    if(y==1)return x;
    if(y%2!=0)return (x*binpow(x,y-1))%MOD;
    ll val=binpow(x,y/2);
    return (val*val)%MOD;
}

void dfs(int root, int v, int par){
    dp[root][v]=1;
    cnt[root][v]=0;
    p[v]=par;
    for(int to:g[v]){
        if(to!=par){
            dfs(root,to,v);
            if(dp[root][to]==1){
                dp[root][v]=0;
                cnt[root][v]++;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("input.txt", "r", stdin);
    cin>>n>>k;
    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<<binpow(4,k)<<endl;
        return 0;
    }
    int c=0;
    for(int v=1;v<=n;v++){
        dfs(v,v,-1);
        c+=dp[v][v];
    }
    ll ans=0;
    for(int v=1;v<=n;v++){
        // for(int u=1;u<=n;u++){
        //     cout<<dp[v][u]<<" ";
        // }
        // cout<<endl;
        bool change=true;
        bool cur=true;
        int u=v;
        while(u!=-1){
            if((cnt[1][u]==1&&!cur)||(cnt[1][u]==0&&cur)){
                cur=!cur;
                u=p[u];
            }
            else{
                change=false;
                break;
            }
        }
        if(!change){
            ans+=n;
        }
        else {
            ans+=(n-c);
        }
    }
    if(dp[1][1]){
        ans=n*n-ans;
    }
    cout<<ans%MOD<<endl;
    return 0;
}

• 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