oj.uz

Submission #701556

# Submission time Handle Problem Language Result Execution time Memory
701556 2023-02-21T13:12:10 Z PCTprobability Star Trek (CEOI20_startrek) C++17
0 / 100
 13 ms 5204 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1000000007;
#define fi first
#define se second
#define pb push_back
ll modPow(ll a,ll b,ll c){
  ll r=1;
  while(b){
    if(b&1) (r*=a)%=mod;
    (a*=a)%=mod;
    b/=2;
  }
  return r;
}
vector<ll> g[100000];
int v[100000];
bool win[100000];
void dfs(ll a,ll b){
  v[a]=1;
  for(auto e:g[a]){
    if(e==b) continue;
    dfs(e,a);
    if(!win[e]) win[a]=true;
    v[a]+=v[e];
  }
}
ll cnt=0;
void dfs2(ll a,ll b,ll x){
  if(x==0) cnt++;
  if(x&&g[a].size()>2) return;
  for(auto e:g[a]){
    if(e==b) continue;
    dfs2(e,a,x^1);
  }
}
ll cnt2=0;
void dfs3(ll a,ll b,ll x){
  if(x) cnt2++;
  if(x==0){
    ll k=0;
    for(auto e:g[a]){
      if(e==b) continue;
      if(!win[e]) k++;
    }
    if(k>=2) return;
  }
  for(auto e:g[a]){
    if(e==b) continue;
    if(x==0&&win[e]) continue;
    dfs3(e,a,x^1);
  }
}
int main(){
  ll n,d;
  cin>>n>>d;
  assert(n<=1000&&d<=100000);
  for(int i=0;i<n-1;i++){
    ll a,b;
    cin>>a>>b;
    a--;
    b--;
    g[a].pb(b);
    g[b].pb(a);
  }
  ll x=0,y=0;
  ll z=0;
  ll type=0,x1=0,y1=0;
  for(int i=0;i<n;i++){
    cnt=0,cnt2=0;
    for(int j=0;j<n;j++) win[j]=false;
    dfs(i,-1);
    ll cn=0,V=0;
    for(auto e:g[i]){
      if(!win[e]){
        cn++;
        V=e;
      }
    }
    if(cn) z++;
    if(cn>=2){
      x++;
    }
    if(cn==1){
      dfs3(V,i,1);
      x+=modPow(n,mod-2,mod)*(n-cnt2);
      x%=mod;
      y+=cnt2;
      y%=mod;
      if(i==0){
        type=1;
        x1+=modPow(n,mod-2,mod)*(n-cnt2);
        y1+=cnt2;
      }
    }
    if(cn==0){
      dfs2(i,-1,0);
      y-=cnt;
      y+=mod;
      y%=mod;
      x+=modPow(n%mod,mod-2,mod)*cnt;
      x%=mod;
      if(i==0){
        type=1;
        x1+=modPow(n%mod,mod-2,mod)*cnt;
        y1-=cnt;
        y1+=mod;
      }
    }
  }
  x1%=mod;
  y1%=mod;
  for(int i=1;i<d;i++){
    z=(z*y + x*modPow(n,2*i,mod));
    z%=mod;
  }
  if(type==0){
    cout<<modPow(n,2*d,mod)<<endl;
  }
  else{
    cout<<(x1*modPow(n,2*d,mod)+y1*z)%mod<<endl;
  }
}

Subtask #1
0.0 / 0.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Runtime error 4 ms 5204 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Incorrect 2 ms 2644 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Incorrect 2 ms 2644 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Incorrect 2 ms 2644 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Incorrect 2 ms 2644 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Incorrect 2 ms 2644 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

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