제출 #490339

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
490339		Wayne_Yan	Star Trek (CEOI20_startrek)	C++17	30 / 100	1095 ms	12152 KiB

startrek

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
typedef int64_t ll;
typedef long double ld;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define RF(n) RFi(i,n)
#define RFi(i,n) RFl(i,0,n)
#define RFl(i,l,n) for(int i=n-1;i>=l;i--)
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define mem(v,x) memset(v,x,sizeof v)
#define ff first
#define ss second
#define mid ((l+r)>>1)
#define RAN(a,b) uniform_int_distribution<int> (a, b)(rng)

template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int mod = 1e9+7;
const int maxN = 1e5+5;
vector<int> edge[maxN];

bool winning[maxN];
bool orig_win[maxN];
void dfs1(int c, int p){
  for(int i : edge[c]){
    if(i == p) continue;
    dfs1(i, c);
    if(winning[i] == false){
      winning[c] = true;
      return;
    }
  }
  winning[c] = false;
}

int expo(int b, int e, int m){
  int ans = 1;
  int tmp = b;
  while(e){
    if(e&1) ans *= tmp;
    ans %= m;
    tmp *= tmp;
    tmp %= m;
    e >>= 1;
  }
  return ans;
}

signed main(){
  
  int n,d;
  cin >> n >> d;
  F(n-1){
    int x,y;
    cin >> x >> y;
    edge[x].pb(y);
    edge[y].pb(x);
  }
  
  if(n == 2 && d != 1){
    printf("%lld", expo(4, (d) % (mod-1), mod));
    return 0;
  }

  int wp = 0;
  int lp = 0;
  Fl(i, 1, n+1){
    fill(winning, winning + n + 5, false);
    dfs1(i, 0);
    if(winning[i]) wp++;
    else lp++;

    if(i == 1){
      Fl(j, 1, 1+n){
        orig_win[j] = winning[j];
      }
    }
  }


  
  int ans = 0;

  Fl(i, 1, n+1){
    fill(winning, winning + n + 5, false);
    edge[i].pb(n+1);
    edge[n+1].pb(i);
    dfs1(1, 0);

    if(orig_win[1] != winning[1]){
      if(orig_win[1]){
        ans += wp;
      }else{
        ans += lp;
      }
    }else{
      if(orig_win[1]) ans += n;
    }
    edge[i].pop_back();
    edge[n+1].pop_back();
  }
  
  printf("%lld", ans);


  return 0;
}

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