oj.uz

Submission #490339

# Submission time Handle Problem Language Result Execution time Memory
490339 2021-11-27T08:34:17 Z Wayne_Yan Star Trek (CEOI20_startrek) C++17
30 / 100
 1000 ms 12152 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];
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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Incorrect 9 ms 2700 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 1 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
8.0 / 8.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 2 ms 2648 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 2 ms 2648 KB Output is correct

Subtask #4
15.0 / 15.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 2 ms 2648 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 2 ms 2648 KB Output is correct
7 Correct 6 ms 2648 KB Output is correct
8 Correct 31 ms 2672 KB Output is correct
9 Correct 16 ms 2636 KB Output is correct
10 Correct 11 ms 2636 KB Output is correct
11 Correct 23 ms 2708 KB Output is correct

Subtask #5
0 / 15.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 2 ms 2648 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 2 ms 2648 KB Output is correct
7 Correct 6 ms 2648 KB Output is correct
8 Correct 31 ms 2672 KB Output is correct
9 Correct 16 ms 2636 KB Output is correct
10 Correct 11 ms 2636 KB Output is correct
11 Correct 23 ms 2708 KB Output is correct
12 Execution timed out 1095 ms 12152 KB Time limit exceeded
13 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 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 2 ms 2648 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 2 ms 2648 KB Output is correct
7 Correct 6 ms 2648 KB Output is correct
8 Correct 31 ms 2672 KB Output is correct
9 Correct 16 ms 2636 KB Output is correct
10 Correct 11 ms 2636 KB Output is correct
11 Correct 23 ms 2708 KB Output is correct
12 Correct 1 ms 2636 KB Output is correct
13 Incorrect 9 ms 2700 KB Output isn't correct
14 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 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 2 ms 2648 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 2 ms 2648 KB Output is correct
7 Correct 6 ms 2648 KB Output is correct
8 Correct 31 ms 2672 KB Output is correct
9 Correct 16 ms 2636 KB Output is correct
10 Correct 11 ms 2636 KB Output is correct
11 Correct 23 ms 2708 KB Output is correct
12 Execution timed out 1095 ms 12152 KB Time limit exceeded
13 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 9 ms 2700 KB Output isn't correct