oj.uz

Submission #791607

# Submission time Handle Problem Language Result Execution time Memory
791607 2023-07-24T07:58:21 Z peteza Star Trek (CEOI20_startrek) C++14
15 / 100
 21 ms 9996 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Runtime error 7 ms 9996 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 15 ms 5008 KB Output is correct
3 Correct 21 ms 4948 KB Output is correct
4 Correct 10 ms 4948 KB Output is correct
5 Correct 13 ms 5012 KB Output is correct
6 Correct 12 ms 5016 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 15 ms 5008 KB Output is correct
3 Correct 21 ms 4948 KB Output is correct
4 Correct 10 ms 4948 KB Output is correct
5 Correct 13 ms 5012 KB Output is correct
6 Correct 12 ms 5016 KB Output is correct
7 Runtime error 7 ms 9940 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 15 ms 5008 KB Output is correct
3 Correct 21 ms 4948 KB Output is correct
4 Correct 10 ms 4948 KB Output is correct
5 Correct 13 ms 5012 KB Output is correct
6 Correct 12 ms 5016 KB Output is correct
7 Runtime error 7 ms 9940 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 15 ms 5008 KB Output is correct
3 Correct 21 ms 4948 KB Output is correct
4 Correct 10 ms 4948 KB Output is correct
5 Correct 13 ms 5012 KB Output is correct
6 Correct 12 ms 5016 KB Output is correct
7 Runtime error 7 ms 9940 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 15 ms 5008 KB Output is correct
3 Correct 21 ms 4948 KB Output is correct
4 Correct 10 ms 4948 KB Output is correct
5 Correct 13 ms 5012 KB Output is correct
6 Correct 12 ms 5016 KB Output is correct
7 Runtime error 7 ms 9940 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Runtime error 7 ms 9996 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -