Submission #490329

#	Time	Username	Problem	Language	Result	Execution time	Memory
490329		Wayne_Yan	Star Trek (CEOI20_startrek)	C++17	7 / 100	2 ms	2672 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];

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);
  }
  
  dfs1(1,0);
  
  if(n == 2){
    printf("%lld", expo(4, (d) % (mod-1), mod));
    return 0;
  }

  printf("4");
  return 0;
}

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