Submission #791607

#	Time	Username	Problem	Language	Result	Execution time	Memory
791607		peteza	Star Trek (CEOI20_startrek)	C++14	15 / 100	21 ms	9996 KiB

startrek

#include <bits/stdc++.h>
using namespace std;
long long mod = 1e9+7;
long long n, d;
int a, b;
bool dp[200005];
vector<int> adj[200005];

bool dfs(int x, bool turn, int par = -1) {
    bool cstate;
    if(turn) {
        cstate = 0;
        for(int e:adj[x]) {
            if(e == par) continue;
            cstate |= dfs(e, !turn, x);
        }
    } else {
        cstate = 1;
        for(int e:adj[x]) {
            if(e == par) continue;
            cstate &= dfs(e, !turn, x);
        }
    }
    return cstate;
}
long long custompow(long long x, long long y) {
    long long res = 1;
    for(;y;y>>=1,x=x*x%mod) if(y&1) res = res*x%mod;
    return res;
}
int main() {
    cin >> n >> d;
  	if(n == 2) {
      cout << custompow(2, 2*d);
      return 0;
    }
    assert(n <= 100 && d == 1);
    for(int i=1;i<n;i++) {
        cin >> a >> b;
        adj[a].push_back(b); adj[b].push_back(a);
        adj[a+100].push_back(b+100); adj[b+100].push_back(a+100);
    }
    int ans = 0;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            adj[i].push_back(j+100);
            ans += dfs(1, 1);
            adj[i].pop_back();
        }
    }
    cout << ans;
}

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