oj.uz

Submission #757574

# Submission time Handle Problem Language Result Execution time Memory
757574 2023-06-13T11:07:24 Z gagik_2007 Star Trek (CEOI20_startrek) C++17
7 / 100
 15 ms 5200 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 15 ms 5200 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 356 KB Output is correct
2 Incorrect 1 ms 852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 356 KB Output is correct
2 Incorrect 1 ms 852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 356 KB Output is correct
2 Incorrect 1 ms 852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 356 KB Output is correct
2 Incorrect 1 ms 852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 356 KB Output is correct
2 Incorrect 1 ms 852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 15 ms 5200 KB Output isn't correct
3 Halted 0 ms 0 KB -