oj.uz

Submission #597162

# Submission time Handle Problem Language Result Execution time Memory
597162 2022-07-15T16:07:02 Z jasmin Star Trek (CEOI20_startrek) C++14
0 / 100
 1 ms 212 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int mod=1e9+7;

vector<int> win_down;
vector<int> redchild;
bool dfs_win(int v, int p, vector<vector<int> >& adi){
    for(auto u: adi[v]){
        if(u==p) continue;

        if(!dfs_win(u, v, adi)){
            redchild[v]=u;
            win_down[v]++;
        }
    }
    return win_down[v]>0;
}
vector<bool> win_up;
int violet=0;
void dfs_win2(int v, int p, vector<vector<int> >& adi){
    if(p==-1){
        win_up[v]=false;
    }
    else if(win_down[v]){
        if(win_down[p]==0 && !win_up[p]){
            win_up[v]=true;
        }
        else{
            win_up[v]=false;
        }
    }
    else if(win_down[v]==0){
        if(win_down[p]==1 && !win_up[p]){
            win_up[v]=true;
        }
        else{
            win_up[v]=false;
        }
    }
    if(!win_up[v] && !win_down[v]) violet++;

    for(auto u: adi[v]){
        if(u!=p) dfs_win2(u, v, adi);
    }
}

int redforce=0;
void dfs(int v, int p, vector<vector<int> >& adi){

    if(win_down[v]==0){
        redforce++;
        for(auto u: adi[v]){
            if(u!=p) dfs(u, v, adi);
        }
    }
    else if(win_down[v]==1){
        dfs(redchild[v], v, adi);
    }
}

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

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

    win_up.resize(n, 0);
    redchild.resize(n, -1);
    win_down.resize(n, 0);
    dfs_win(0, -1, adi);
    dfs_win2(0, -1, adi);
    dfs(0, -1, adi);

   
    int ans=(n*n - redforce*violet)%mod;
    cout << ans << "\n";
}

Subtask #1
0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -