oj.uz

Submission #791567

# Submission time Handle Problem Language Result Execution time Memory
791567 2023-07-24T07:29:29 Z ttamx Star Trek (CEOI20_startrek) C++14
30 / 100
 1000 ms 10652 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N=1e5+5;
const ll mod=1e9+7;

ll binpow(ll a,ll b){
    ll res=1;
    while(b>0){
        if(b&1)res*=a,res%=mod;
        a*=a,a%=mod;
        b>>=1;
    }
    return res;
}

int n;
ll d,ans,sum;
vector<int> adj[N];
ll dp[N][2];
bool dp1[N],dp2[N];

void dfs(int u,int p){
    for(auto v:adj[u]){
        if(v==p)continue;
        dfs(v,u);
        dp1[u]|=!dp1[v];
    }
}

void dfs2(int u,int p,bool w){
    int cnt=!w;
    dp2[u]=dp1[u]|!w;
    for(auto v:adj[u]){
        if(v==p)continue;
        cnt+=!dp1[v];
    }
    for(auto v:adj[u]){
        if(v==p)continue;
        dfs2(v,u,cnt-!dp1[v]>0);
    }
}

bool dfs3(int u,int p,int t,bool w){
    bool res=true;
    for(auto v:adj[u]){
        if(v==p)continue;
        res&=dfs3(v,u,t,w);
    }
    if(u==t)res&=w;
    res^=true;
    return res;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> d;
    if(n==2)cout << binpow(4,d),exit(0);
    for(int i=1;i<n;i++){
        int u,v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    dfs(1,1);
    dfs2(1,1,true);
    for(int i=1;i<=n;i++)sum+=dp2[i];
    for(int i=1;i<=n;i++)ans+=sum*dfs3(1,1,i,true)+(n-sum)*dfs3(1,1,i,false);
    cout << ans;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 18 ms 2772 KB Output is correct
8 Correct 24 ms 2780 KB Output is correct
9 Correct 13 ms 2728 KB Output is correct
10 Correct 14 ms 2724 KB Output is correct
11 Correct 14 ms 2724 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 18 ms 2772 KB Output is correct
8 Correct 24 ms 2780 KB Output is correct
9 Correct 13 ms 2728 KB Output is correct
10 Correct 14 ms 2724 KB Output is correct
11 Correct 14 ms 2724 KB Output is correct
12 Execution timed out 1054 ms 10652 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 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 18 ms 2772 KB Output is correct
8 Correct 24 ms 2780 KB Output is correct
9 Correct 13 ms 2728 KB Output is correct
10 Correct 14 ms 2724 KB Output is correct
11 Correct 14 ms 2724 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Incorrect 13 ms 2728 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 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 18 ms 2772 KB Output is correct
8 Correct 24 ms 2780 KB Output is correct
9 Correct 13 ms 2728 KB Output is correct
10 Correct 14 ms 2724 KB Output is correct
11 Correct 14 ms 2724 KB Output is correct
12 Execution timed out 1054 ms 10652 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 2644 KB Output is correct
2 Incorrect 13 ms 2720 KB Output isn't correct
3 Halted 0 ms 0 KB -