답안 #466256

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
466256 2021-08-18T12:16:56 Z ivan_tudor Star Trek (CEOI20_startrek) C++14
0 / 100
7 ms 5344 KB
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int MOD = 1e9 + 7;
int tp[N], tpr[N];
int crit[N], critr[N];
vector<int> gr[N];
void add(long long &x, long long y){
  y%=MOD;
  x+=y;
  if(x>=MOD)
    x-=MOD;
  if(x<0)
    x+=MOD;
}
void add(int &x, long long y){
  y%=MOD;
  x+=y;
  if(x>=MOD)
    x-=MOD;
  if(x<0)
    x+=MOD;
}
void dfs(int nod, int dad){
  tp[nod] = 0;
  int nr0 = 0, sum = 0, unq = 0;
  for(auto x:gr[nod]){
    if(x != dad){
      dfs(x, nod);
      if(tp[x] == 0)
        nr0++, unq = crit[x];
      sum += crit[x];
    }
  }
  if(nr0 == 0){
    tp[nod] = 0;
    crit[nod] = sum + 1;
  }
  else if(nr0 == 1){
    tp[nod] = 1;
    crit[nod] = unq;
  }
  else{
    tp[nod] = 1;
    crit[nod] = 0;
  }
}
void changeroot(int nod, int dad){
  int OLDTP = tp[nod], OLDCRIT = crit[nod];
  int nr0 = 0, sum = 0, unq = 0;
  for(auto x:gr[nod]){
    if(tp[x] == 0 )
      nr0++, unq = crit[x];
    sum += crit[x];
  }
  if(nr0 == 0)
    tp[nod] = 0;
  else
    tp[nod] = 1;
  if(tp[nod] == 0){
    crit[nod] = sum + 1;
  }
  else if(tp[nod] == 1){
    crit[nod] = 0;
    if(nr0 == 1)
      crit[nod] = unq;
  }
  critr[nod] = crit[nod];
  tpr[nod] = tp[nod];

  for(auto x:gr[nod]){
    if(x == dad)
      continue;
    int oldtp = tp[nod], oldcrit = crit[nod];
    if(tp[nod] == 0){
      tp[nod] = 0;
      crit[nod] = sum + 1 - crit[x];
    }
    else{
      if(tp[x] == 1){
        tp[nod] = 1;
        crit[nod] = oldcrit;
      }
      else{
        if(nr0 == 1){
          tp[nod] = 0;
          crit[nod] = sum + 1 - crit[x];
        }
        else if(nr0 == 2){
          tp[nod] = 1;
          int othunq = 0;
          for(auto vc:gr[nod]){
            if(vc == x)
              continue;
            if(tp[vc] == 0)
              othunq = crit[vc];
          }
          crit[nod] = othunq;
        }
        else if(nr0 >= 3){
          tp[nod] = 1;
          crit[nod] = 0;
        }
      }

    }

    changeroot(x, nod);

    tp[nod] = oldtp;
    crit[nod] = oldcrit;
  }

  tp[nod] = OLDTP;
  crit[nod] = OLDCRIT;
}
long long dp[N][2];
int main()
{
  freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n, d;
  cin>>n>>d;
  for(int i = 1; i < n; i++){
    int u, v;
    cin>>u>>v;
    gr[u].push_back(v);
    gr[v].push_back(u);
  }
  dfs(1, 0);
  changeroot(1, 0);
  long long nr0 = 0, sumc0= 0, nr1 = 0, sumc1= 0;
  for(int i = 1; i<=n; i++){
    if(tpr[i] == 0){
      nr0++;
      add(sumc0, critr[i]);
    }
    else{
      nr1++;
      add(sumc1, critr[i]);
    }
    cerr<<tpr[i]<<" "<<critr[i]<<"\n";
  }
  dp[0][0] = nr0;
  dp[0][1] = nr1;
  for(int i = 1; i <d; i++){
    dp[i][0] = 0;
    //vine din 0
    add(dp[i][0], 1LL * sumc0 * dp[i-1][1]);
    add(dp[i][0], 1LL * (1LL*n*n%MOD - sumc0 + MOD)%MOD * ((dp[i-1][0] + dp[i-1][1])%MOD));

    //vine din 1
    add(dp[i][0], 1LL * sumc1 * dp[i-1][0]);

    dp[i][1] = 0;
    //vine din 0
    add(dp[i][1], 1LL * sumc0 * dp[i-1][0]);

    //vine din 1
    add(dp[i][1], 1LL * sumc1 * dp[i - 1][1]);
    add(dp[i][1], 1LL * (1LL*n*n%MOD - sumc1 + MOD)%MOD * ((dp[i-1][0] + dp[i-1][1])%MOD));
  }
  long long ans = 0;
  if(tpr[1] == 0){
    ans = 1LL * critr[1] * dp[d-1][0] % MOD;
  }
  else{
    ans = 1LL * critr[1] * dp[d - 1][1] % MOD;
    add(ans, 1LL * (n - critr[1] + MOD)%MOD * ((dp[d-1][0] + dp[d-1][1])%MOD));
  }
  cout<<ans;
  return 0;
}

Compilation message

startrek.cpp: In function 'int main()':
startrek.cpp:120:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |   freopen(".in","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 5324 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 5304 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 5344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 5344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 5344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 5344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 5344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 5324 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -