oj.uz

Submission #592139

# Submission time Handle Problem Language Result Execution time Memory
592139 2022-07-08T16:06:54 Z jasmin Star Trek (CEOI20_startrek) C++14
15 / 100
 1000 ms 576 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long 

const int mod=1e9+7;

int fastpow(int a, int e){
    if(e==0) return 1;
    int ans=fastpow(a, e/2);
    ans=(ans*ans)%mod;
    if(e%2==1){
        ans=(ans*a)%mod;
    }
    return ans;
}

bool dfs(int v, int p, vector<vector<int> >& adi){

    for(auto u: adi[v]){
        if(u==p) continue;

        if(!dfs(u, v, adi)){
            return true;
        }
    }
    return false;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, d;
    cin >>  n >> d;
    vector<vector<int> > adi(n*2);
    for(int i=0; i<n-1; i++){
        int a, b;
        cin >> a >> b;
        adi[a-1].push_back(b-1);
        adi[a-1+n].push_back(b-1+n);
        adi[b-1].push_back(a-1);
        adi[b-1+n].push_back(a-1+n);
    }

    int ans=0;
    if(n==2){
        ans=fastpow(4, d);
    }
    else{
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                adi[i].push_back(j+n);
                if(dfs(0, -1, adi)){
                    ans++;
                    //cout << i << " " << j << "\n";
                }
                adi[i].pop_back();
            }
        }
    }
    cout << ans << "\n";
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1093 ms 340 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 6 ms 328 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 6 ms 212 KB Output is correct
5 Correct 5 ms 328 KB Output is correct
6 Correct 6 ms 212 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 6 ms 328 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 6 ms 212 KB Output is correct
5 Correct 5 ms 328 KB Output is correct
6 Correct 6 ms 212 KB Output is correct
7 Correct 63 ms 576 KB Output is correct
8 Execution timed out 1088 ms 468 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 6 ms 328 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 6 ms 212 KB Output is correct
5 Correct 5 ms 328 KB Output is correct
6 Correct 6 ms 212 KB Output is correct
7 Correct 63 ms 576 KB Output is correct
8 Execution timed out 1088 ms 468 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 6 ms 328 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 6 ms 212 KB Output is correct
5 Correct 5 ms 328 KB Output is correct
6 Correct 6 ms 212 KB Output is correct
7 Correct 63 ms 576 KB Output is correct
8 Execution timed out 1088 ms 468 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 6 ms 328 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 6 ms 212 KB Output is correct
5 Correct 5 ms 328 KB Output is correct
6 Correct 6 ms 212 KB Output is correct
7 Correct 63 ms 576 KB Output is correct
8 Execution timed out 1088 ms 468 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1093 ms 340 KB Time limit exceeded
3 Halted 0 ms 0 KB -