Submission #466279

#	Time	Username	Problem	Language	Result	Execution time	Memory
466279		ivan_tudor	Star Trek (CEOI20_startrek)	C++14	100 / 100	785 ms	23324 KiB

startrek

#include<bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 5;
const long long MOD = 1e9 + 7;
long long tp[N], tpr[N];
long long 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 dfs(long long nod, long long dad){
  tp[nod] = 0;
  long long 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(long long nod, long long dad){
  long long OLDTP = tp[nod], OLDCRIT = crit[nod];
  long long 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;
    long long 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;
          long long 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 mat[2][2];
long long aux[2][2];
long long rez[2][2];

void multiply(long long A[2][2], long long B[2][2], long long rez[2][2]){
  for(long long i = 0; i < 2; i++)
    for(long long j = 0; j < 2; j++)
      rez[i][j] = 0;
  for(long long i = 0; i <2; i++){
    for(long long j = 0; j < 2; j++){
      for(long long k = 0; k < 2; k++){
        add(rez[i][j], 1LL * A[i][k] * B[k][j]);
      }
    }
  }

}
void cpy(long long A[2][2], long long B[2][2]){
  for(long long i = 0; i < 2; i++){
    for(long long j = 0; j < 2; j++){
      B[i][j] = A[i][j];
    }
  }
}
void mknull(long long A[2][2]){
  for(long long i = 0; i < 2; i++){
    for(long long j = 0; j < 2; j++){
      A[i][j] = 0;
    }
  }
  A[0][0] = A[1][1] = 1;
}
void lgcput(long long pwr){
  mknull(rez);
  while(pwr){
    if(pwr & 1){
      multiply(mat, rez, aux);
      cpy(aux, rez);
    }
    multiply(mat, mat, aux);
    cpy(aux, mat);
    pwr/=2;
  }
}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  long long n, d;
  cin>>n>>d;
  for(long long i = 1; i < n; i++){
    long long 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(long long 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";
  }
  mat[0][0] = 1LL *(1LL * n * nr0 + sumc1 - sumc0 + MOD)%MOD;
  mat[0][1] = 1LL *(1LL * n * nr1 + sumc0 - sumc1 + MOD)%MOD;
  mat[1][0] = 1LL * n * nr0 % MOD;
  mat[1][1] = 1LL * n * nr1 % MOD;
  lgcput(d - 1);
  // puterea se afla in rez
  mat[0][0] = nr0;
  mat[0][1] = nr1;
  mat[1][0] = mat[1][1] = 0;

  multiply(mat, rez, aux);
  long long ans = 0;
  if(tpr[1] == 0){
    ans = 1LL * critr[1] * aux[0][0] % MOD;
  }
  else{
    ans = 1LL * critr[1] * aux[0][1] % MOD;
    add(ans, 1LL * (n - critr[1] + MOD)%MOD * ((aux[0][0] + aux[0][1])%MOD));
  }
  cout<<ans;
  return 0;
}

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