oj.uz

Submission #490337

# Submission time Handle Problem Language Result Execution time Memory
490337 2021-11-27T08:24:00 Z Wayne_Yan Star Trek (CEOI20_startrek) C++17
7 / 100
 7 ms 2636 KB 
#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);
  }
  if(n == 2){
    printf("%lld", expo(4, (d) % (mod-1), mod));
    return 0;
  }

  dfs1(1,0);

  int wp = 0;
  int lp = 0;
  Fl(i, 1, n+1){
    if(winning[i]) wp++;
    else lp++;
  }
  
  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(winning[1]) ans += lp;
    edge[i].pop_back();
    edge[n+1].pop_back();
  }
  
  printf("%lld", ans);


  return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Incorrect 7 ms 2636 KB Output isn't correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct

Subtask #3
0 / 8.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Incorrect 7 ms 2636 KB Output isn't correct